在由若干 0 和 1 组成的数组 A 中，有多少个和为 S 的非空子数组。
样例:
输入：A = [1,0,1,0,1], S = 2
输出：4
解释：
如下面黑体所示，有 4 个满足题目要求的子数组：
[1,0,1]
[1,0,1]
[1,0,1,0]
[0,1,0,1]
主要考察前缀和以及哈希
class Solution:
"""
@param A: an array
@param S: the sum
@return: the number of non-empty subarrays
"""
def numSubarraysWithSum(self, A, S):
# Write your code here.
if not A:
return 0
counter=collections.Counter()
prefix,res=0,0
counter[0]=1
for i in A:
prefix+=i
if prefix>=S:
res+=counter[prefix-S]
counter[prefix]+=1
return res
