Binary Subarrays With Sum
In an array A
of 0
s and 1
s, 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:
A.length <= 30000
0 <= S <= A.length
A[i]
is either0
or1
.
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