ধরুন আমাদের কাছে অ-ঋণাত্মক সংখ্যার একটি তালিকা এবং একটি টার্গেট পূর্ণসংখ্যা k আছে, আমাদেরকে একটি ফাংশন লিখতে হবে যে অ্যারের আকারের একটি অবিচ্ছিন্ন সাবয়ারে আছে কিনা তা পরীক্ষা করতে হবে কমপক্ষে 2 যা k এর গুণিতক পর্যন্ত যোগফল, n * পর্যন্ত যোগফল। k যেখানে nও একটি পূর্ণসংখ্যা। সুতরাং যদি ইনপুটটি [23,2,4,6,7], এবং k =6 এর মত হয়, তবে ফলাফলটি সত্য হবে, কারণ [2,4] আকার 2 এর একটি অবিচ্ছিন্ন সাবয়ারে এবং 6 পর্যন্ত যোগফল।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি মানচিত্র m তৈরি করুন, m[0] সেট করুন :=-1 এবং যোগফল :=0, n :=সংখ্যা বিন্যাসের আকার
- আমি 0 থেকে n – 1
- পরিসরে
- সমষ্টি :=যোগফল + সংখ্যা[i]
- যদি k অ শূন্য হয়, তাহলে যোগফল :=যোগ মোড k
- যদি m-এর যোগফল থাকে এবং i – m[sum]>=2 থাকে, তাহলে true ফেরত দিন
- যদি m-এর যোগফল না থাকে, m[sum] :=i সেট করুন
- মিথ্যে ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
unordered_map<int, int> m;
m[0] = -1;
int sum = 0;
int n = nums.size();
for(int i = 0; i < n; i++){
sum += nums[i];
if(k)
sum %= k;
if(m.count(sum) && i - m[sum] >= 2){
return true;
}
if(!m.count(sum)) m[sum] = i;
}
return false;
}
};
main(){
vector<int> v = {23,2,4,6,7};
Solution ob;
cout << (ob.checkSubarraySum(v, 6));
} ইনপুট
[23,2,4,6,7] 6
আউটপুট
1
