Binary Subarrays With Sum trong C++

Cho mảng A chỉ chứa 0 và 1, đếm số subarray không rỗng có tổng bằng S.

Ví dụ: [1,0,1,0,1], S=2 → 4.

Giải pháp: số subarray có tổng = S bằng atMost(S) - atMost(S-1). Hàm atMost(x) dùng cửa sổ trượt đếm subarray có tổng ≤ x.

• atMost(x): nếu x<0 return 0; j=0, ret=0

• For i=0..n-1: x-=A[i]; while x<0: x+=A[j], j++; ret+=i-j+1

• Return ret

Ví dụ

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

Đầu vào

[1,0,1,0,1]

Đầu ra

4