# 930. 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]
[1,0,1,0]
[0,1,0,1]
[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(vector<int>& A, int S) {
int res = 0, curSum = 0;
unordered_map<int, int> m{{0, 1}};
for (int num : A) {
curSum += num;
res += m[curSum - S];
++m[curSum];
}
return res;
}
};
``````

``````class Solution {
public:
int numSubarraysWithSum(vector<int>& A, int S) {
int res = 0, sum = 0, left = 0, n = A.size();
for (int i = 0; i < n; ++i) {
sum += A[i];
while (left < i && sum > S) sum -= A[left++];
if (sum < S) continue;
if (sum == S) ++res;
for (int j = left; j < i && A[j] == 0; ++j) {
++res;
}
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/930

https://leetcode.com/problems/binary-subarrays-with-sum/

https://leetcode.com/problems/binary-subarrays-with-sum/discuss/276976/C%2B%2B

https://leetcode.com/problems/binary-subarrays-with-sum/discuss/186683/C%2B%2BJavaPython-Sliding-Window-O(1)-Space

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation