C++ में बाइनरी सबएरे विद सम (Binary Subarrays With Sum)

मान लीजिए 0s और 1s का एक ऐरे A दिया गया है, हमें गैर-खाली उपसरणियों की संख्या खोजनी है जिनका योग S है? उदाहरण के लिए, यदि इनपुट [1,0,1,0,1] है और S = 2, तो परिणाम 4 होगा।

समाधान दृष्टिकोण

1. atMost() विधि परिभाषित करें जो अधिकतम x योग वाली उपसरणियां गिनती है

2. स्लाइडिंग विंडो से j पॉइंटर एडजस्ट करें

3. ret += i - j + 1 से गिनती जोड़ें

4. मुख्य विधि से: atMost(S) - atMost(S-1) लौटाएं

C++ कार्यान्वयन

#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); 
    } 
}; 

int main(){ 
    vector<int> v1 = {1,0,1,0,1}; 
    Solution ob; 
    cout << (ob.numSubarraysWithSum(v1, 2)); 
    return 0; 
}

इनपुट

[1,0,1,0,1]

आउटपुट

4