ধরুন 0 এবং 1s এর একটি অ্যারে দেওয়া হল, আমাদের খুঁজে বের করতে হবে কতগুলি অ-খালি সাবয়ারের যোগফল S আছে? সুতরাং যদি ইনপুট হয় [1,0,1,0,1], এবং S =2, তাহলে ফলাফল হবে 4, যেমন সাবয়ারেগুলি [1,0,1,0,1], [1,0 ,1,0,1], [1,0,1,0,1], [1,0,1,0,1]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
atMost() নামক একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি অ্যারে A এবং পূর্ণসংখ্যা x
নেবে -
যদি x <0 হয়, তাহলে 0 ফেরত দিন, j :=0 সেট করুন এবং ret :=0
সেট করুন -
আমি 0 থেকে A
এর পরিসরে-
A[i]
দ্বারা x হ্রাস করুন -
যখন x <0
-
x বাড়িয়ে A[j], j বাড়ান 1
-
-
ret :=ret + i – j + 1
-
-
রিটার্ন রিটার্ন
-
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
ret :=atMost(A, S) – atMost(A, S – 1)
-
রিটার্ন রিটার্ন
আরও ভাল বোঝার জন্য আসুন আমরা নিম্নলিখিত বাস্তবায়ন দেখি &mius;
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int atMost(vector <int>& A, int x){
if(x < 0) return 0;
int j = 0;
int ret = 0;
for(int i = 0; i < A.size(); i++){
x -= A[i];
while(x < 0){
x += A[j];
j++;
}
ret += i - j + 1;
}
return ret;
}
int numSubarraysWithSum(vector<int>& A, int S) {
return atMost(A, S) - atMost(A, S - 1);
}
};
main(){
vector<int> v1 = {1,0,1,0,1};
Solution ob;
cout << (ob.numSubarraysWithSum(v1, 2));
} ইনপুট
[1,0,1,0,1]
আউটপুট
4
