C ++中具有和的二进制子数组
假设给定的数组A为0和1，我们必须找到多少个非空子数组的总和为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的i
将x增加A[j]，将j增加1
将x减少A[i]
而x<0
ret：=ret+i–j+1
返回ret
从主要方法中执行以下操作-
ret：=atMost(A,S)–atMost（A，S–1）
返回ret
让我们看下面的实现，以更好地理解＆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