Binary Subarrays With Sum ใน C++

คำอธิบายปัญหา

กำหนดอาร์เรย์ A ของ 0 และ 1 ต้องการหาจำนวน subarray ที่มีผลรวมเท่ากับ S

ตัวอย่าง: [1,0,1,0,1], S=2 → 4 subarrays

วิธีแก้ปัญหา (Sliding Window / Prefix Sum)

ใช้ฟังก์ชัน atMost(x) = จำนวน subarray ที่ผลรวม <= x

คำตอบ = atMost(S) - atMost(S-1)

1. atMost(x): sliding window ขยายขวา, หาผลรวม > x ย่อซ้าย
2. สะสมจำนวน subarray ที่จบที่ i

ตัวอย่างโค้ด C++

#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, ret = 0, sum = 0;
        for(int i = 0; i < A.size(); i++) {
            sum += A[i];
            while(sum > x) {
                sum -= A[j];
                j++;
            }
            ret += i - j + 1;
        }
        return ret;
    }
    
    int numSubarraysWithSum(vector<int>& A, int S) {
        return atMost(A, S) - atMost(A, S - 1);
    }
};

int main() {
    vector<int> v1 = {1,0,1,0,1};
    Solution ob;
    cout << ob.numSubarraysWithSum(v1, 2);
    return 0;
}

อินพุต

[1,0,1,0,1] 2

เอาต์พุต

4