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