ধরুন আমাদের কাছে পূর্ণসংখ্যার একটি অ্যারে এবং একটি পূর্ণসংখ্যা k আছে, আমাদের মোট অবিচ্ছিন্ন সাবয়ারের সংখ্যা খুঁজে বের করতে হবে যার যোগফল k এর সমান। তাই যদি সংখ্যা অ্যারে হয় [1, 1, 1] এবং k হয় 2, তাহলে আউটপুট হবে 2।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি মানচিত্র সংজ্ঞায়িত করুন যাকে বলা হয় যোগফল, তাপমাত্রা :=0, যোগফল[0] :=1 এবং উত্তর :=0
- এর জন্য আমি 0 থেকে অ্যারের আকারের পরিসরে
- temp :=temp + n[i]
- যদি যোগফলের k – temp থাকে, তাহলে
- উত্তর :=ans + যোগফল[k - temp]
- অর্থের মান [-temp] 1 দ্বারা বৃদ্ধি করুন
- উত্তর ফেরত দিন
উদাহরণ(C++)
আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int subarraySum(vector<int>& n, int k) {
unordered_map <int, int> sums;
int temp = 0;
sums[0] = 1;
int ans =0;
for(int i =0;i<n.size();i++){
temp+= n[i];
if(sums.find(k-temp)!=sums.end()){
ans += sums[k-temp];
}
sums[-temp]++;
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {1,1,1};
cout << (ob.subarraySum(v, 2));
} ইনপুট
৷[1,1,1] 2
আউটপুট
2
