# 930. Binary Subarrays With Sum 和相同的二元子数组

@TOC

## # 题目描述

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:

1. A.length <= 30000
2. 0 <= S <= A.length
3. A[i] is either 0 or 1.

## # 解题方法

### # 二分查找

``````class Solution(object):
def numSubarraysWithSum(self, A, S):
"""
:type A: List[int]
:type S: int
:rtype: int
"""
N = len(A)
tsum = [0] * (N + 1)
for i in range(1, N + 1):
tsum[i] = tsum[i - 1] + A[i - 1]
res = 0
for i in range(1, N + 1):
remain = tsum[i] - S
if remain < 0:
continue
left = bisect.bisect_left(tsum, remain)
right = bisect.bisect_right(tsum, remain)
right = min(i, right)
res += right - left
return res
``````

### # 字典

560. Subarray Sum Equals Kopen in new window几乎一模一样的题目，为什么就是不会做呢？

``````class Solution(object):
def numSubarraysWithSum(self, A, S):
"""
:type A: List[int]
:type S: int
:rtype: int
"""
N = len(A)
res = 0
preS = 0
count = collections.Counter({0 : 1})
for i in range(1, N + 1):
preS += A[i - 1]
res += count[preS - S]
count[preS] += 1
return res
``````

## # 相似题目

560. Subarray Sum Equals Kopen in new window

## # 参考资料

https://leetcode.com/problems/binary-subarrays-with-sum/discuss/186683/C++JavaPython-Straight-Forward

## # 日期

2018 年 10 月 28 日 —— 啊，悲伤的周赛