Binary Subarrays With Sum

In an array A of 0s and 1s, how many non-empty subarrays have sum S?

Example 1:

Input: A = [1,0,1,0,1], S = 2
Output: 4
Explanation: 
The 4 subarrays are bolded below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]

Note:

  1. A.length <= 30000

  2. 0 <= S <= A.length

  3. A[i] is either 0 or 1.

class Solution {
    public int numSubarraysWithSum(int[] A, int S) {
        return atMost(A, S) - atMost(A, S - 1);
    }

    // Using at most sum -> S function
    public int atMost(int[] A, int S) {
        if (S < 0)
            return 0;
        int ans = 0, start = 0, currSum = 0;
        for (int end = 0; end < A.length; end++) {
            currSum += A[end];
            while (currSum > S)
                currSum -= A[start++];
            ans += end - start + 1;
        }
        return ans;
    }
}

Last updated