在由若干 0 和 1 組成的數(shù)組 A 中，有多少個和為 S 的非空子數(shù)組。

樣例:

輸入：A = [1,0,1,0,1], S = 2
輸出：4
解釋：
如下面黑體所示，有 4 個滿足題目要求的子數(shù)組：
[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