和相同的二元子数组

https://www.lintcode.com/problem/1712/description?utm_source=sc-cheatsheet-cyc

描述

在由若干 0 和 1 组成的数组 A 中，有多少个和为 S 的非空子数组。

• A.length <= 30000

• 0 <= S <= A.length

• A[i] 为 0 或 1

样例

样例 1:

输入：A = [1,0,1,0,1], S = 2输出：4解释：如下面黑体所示，有 4 个满足题目要求的子数组：[1,0,1][1,0,1][1,0,1,0][0,1,0,1]

样例 2:

输入：A = [0,0,0,0,0,0,1,0,0,0], S = 0输出：27解释：和为 S 的子数组有 27 个

分析

presum Map存presum的个数 presum={0:1}

遍历时， 若prefix_sum - S 存在，说明有prefix_count[prefix_sum - S] subarrays that sum to S.

            count += prefix_count[prefix_sum - S]
            

```python
from typing import (
    List,
)

class Solution:
    """
    @param a: an array
    @param s: the sum
    @return: the number of non-empty subarrays
    """
    def num_subarrays_with_sum(self, a: List[int], s: int) -> int:
        # Write your code here.
        presum = {0:1} #某个sum出现的次数
        cursum = 0
        res = 0
        for i in a:
            cursum += i
            if cursum - s in presum:
                res += presum[cursum - s]
            presum[cursum] = presum.get(cursum, 0) + 1
            
        return res

```