Binary Subarrays Với Sum trong C ++

Giả sử cho một mảng A gồm các số 0 và 1, chúng ta phải tìm xem có bao nhiêu mảng con không rỗng có tổng S? Vì vậy, nếu đầu vào là [1,0,1,0,1] và S =2, thì kết quả sẽ là 4, vì các mảng con là [1,0,1,0,1], [1,0 , 1,0,1], [1,0,1,0,1], [1,0,1,0,1].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một phương thức được gọi là atMost (), phương thức này sẽ nhận mảng A và số nguyên x

• nếu x <0, thì trả về 0, đặt j:=0 và đặt ret:=0

• cho tôi trong phạm vi từ 0 đến kích thước của A

  • giảm x đi A [i]

  • trong khi x <0

    • tăng x lên A [j], tăng j thêm 1

  • ret:=ret + i - j + 1

• trả lại ret

• Từ phương thức chính, thực hiện như sau -

• ret:=atMost (A, S) - atMost (A, S - 1)

• trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn &mius;

Ví dụ

#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));
}

Đầu vào

[1,0,1,0,1]

Đầu ra

4