C++에서 합계가 있는 이진 부분배열

<시간/>

0과 1의 배열 A가 주어졌다고 가정하고, 우리는 합이 S인 비어 있지 않은 하위 배열이 몇 개나 찾아야 할까요? 따라서 입력이 [1,0,1,0,1]이고 S =2인 경우 하위 배열이 [1,0,1,0,1], [1,0]이므로 결과는 4가 됩니다. ,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에 대해
- A[i]만큼 x 감소
- 동안 x <0
  - A[j]만큼 x 증가, 1만큼 j 증가
- 렛 :=렛 + i – j + 1
리턴 렛
주요 방법에서 다음을 수행하십시오 -
ret :=atMost(A, S) – atMost(A, S – 1)
리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. &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]

C++에서 합계가 있는 이진 부분배열

예시

입력

출력