二进制子数组和问题

题目描述： 给定一个仅包含 0 和 1 的数组，找到该数组中和为给定值 S 的所有子数组的数量。

示例： 输入: nums = [1,0,1,0,1], S = 2 输出: 4 解释: 如下面所示，有 4 个满足题意的子数组： [1,0,1,0,1] [1,0,1,0,1] [1,0,1,0,1] [1,0,1,0,1]

解决思路： 使用前缀和(preSum)加哈希表的想法。 对于数组nums，构建一个前缀和数组preSum， preSum[i]表示nums中前i个数的和。 则(i,j]（i不包括）对应的子数组和为 sum = preSum[j] - preSum[i]。 如果找到一个位置j，满足preSum[j] - preSum[i] == S，则子数组[i+1:j]的和为S。 我们只需要记录下出现过的preSum[i]数量，容易证明对于当前j所在位置，满足条件的子数组数量就为哈希表中preSum[j] - S的数量。

代码示例： class Solution: def numSubarraysWithSum(self, nums: List[int], S: int) -> int: preSum = 0 count = collections.Counter() res = 0 for num in nums: count[preSum] += 1 preSum += num res += count[preSum - S] return res