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
热门推荐
10 医院探望朋友祝福语简短
11 毕业祝福语简短女朋友
12 春节虎年爸妈祝福语简短
13 儿童毕业祝福语 简短6
14 开工仪式横幅祝福语简短
15 孩子日常祝福语大全简短
16 清晨寄语诗句祝福语简短
17 结婚送亲认亲祝福语简短
18 虎年喝酒拜年祝福语简短