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:
A.length <= 30000
0 <= S <= A.length
A[i] is either 0 or 1.
Solution:
count number of subarrays that sum to less or equal a number first
class Solution {
public int numSubarraysWithSum(int[] A, int S) {
return numSubarraysLessAndEqualToSum(A, S) - numSubarraysLessAndEqualToSum(A, S - 1);
}
private int numSubarraysLessAndEqualToSum(int[] arr, int S) {
int left = 0;
int right = 0;
int count = 0;
int sum = 0;
while (right < arr.length) {
sum += arr[right];
while (left <= right && sum > S) {
sum -= arr[left];
left ++;
}
count += right - left + 1;
right ++;
}
return count;
}
}