C++で合計を使用するバイナリサブアレイ

0と1の配列Aが与えられたとすると、合計Sを持つ空でないサブ配列の数を見つける必要がありますか？したがって、入力が[1,0,1,0,1]のようで、S =2の場合、サブ配列は[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[i]

    減らす

  • x <0

    • xをA[j]増やし、jを1増やします

  • 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