二进制数组和为 S 的子数组个数，前缀和哈希和滑动窗口各怎么做？

简化版

二进制数组和为 S 的子数组可以用前缀和哈希统计。

遍历时维护前缀和 sum，以当前下标结尾且和为 S 的子数组数量，等于之前出现过的 sum - S 次数。

因为数组只有 0 和 1，也可以用“至多 S 的子数组数 - 至多 S-1 的子数组数”做滑动窗口。

详细版

前缀和做法最通用：

ans += count.get(sum - goal) || 0
count.set(sum, (count.get(sum) || 0) + 1)

初始化 count.set(0, 1)，表示空前缀出现过一次。

如果使用滑动窗口，需要利用二进制数组非负的性质。定义 atMost(goal) 表示和不超过 goal 的子数组个数，那么和恰好为 goal 的数量是：

atMost(goal) - atMost(goal - 1)

前缀和更容易泛化，滑动窗口在非负数组上也很高效。

完整版教学

一、为什么前缀和可以统计个数

设当前位置前缀和为 sum。如果某个更早的前缀和是 sum - goal，那么两者之间的子数组和就是 goal。和“是否存在”不同，这里要统计数量，所以哈希表里存的是某个前缀和出现过多少次。

记忆钩子：求个数存次数，求最长存最早位置，别把两个模板混了。

二、前缀和哈希的流程

每到一个位置，先把当前元素加入 sum，再查询 sum - goal 出现次数，把它加到答案中。最后再把当前 sum 计入哈希表。顺序不能乱，因为我们统计的是之前前缀到当前前缀之间的子数组。

function numSubarraysWithSum(nums, goal) {
  const count = new Map([[0, 1]])
  let sum = 0
  let ans = 0
  for (const x of nums) {
    sum += x
    ans += count.get(sum - goal) || 0
    count.set(sum, (count.get(sum) || 0) + 1)
  }
  return ans
}

这个写法能自然处理 goal = 0。

三、带数字推演

数组 [1,0,1,0,1]，goal = 2。

初始 count[0]=1
读 1: sum=1，找 -1，无
读 0: sum=1，找 -1，无，count[1] 变 2
读 1: sum=2，找 0，有 1 个，ans=1
读 0: sum=2，找 0，有 1 个，ans=2
读 1: sum=3，找 1，有 2 个，ans=4

答案是 4。

四、为什么也能用 atMost 滑动窗口

二进制数组元素非负，所以窗口和随右扩不会下降，左缩不会上升。可以统计“和最多为 K 的子数组个数”。恰好等于 goal 的数量，就等于最多 goal 的数量减去最多 goal-1 的数量。

统计对象	含义
`atMost(goal)`	和为 `0..goal` 的子数组
`atMost(goal-1)`	和为 `0..goal-1` 的子数组
差值	和恰好为 `goal` 的子数组

这是“恰好 K = 至多 K - 至多 K-1”的常见技巧。

五、滑动窗口代码

实现如下：

function atMost(nums, goal) {
  if (goal < 0) return 0
  let left = 0
  let sum = 0
  let ans = 0
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right]
    while (sum > goal) sum -= nums[left++]
    ans += right - left + 1
  }
  return ans
}

function numSubarraysWithSum(nums, goal) {
  return atMost(nums, goal) - atMost(nums, goal - 1)
}

如果面试官问泛化到有负数，前缀和哈希更稳。

六、常见误区与追问

误区：哈希表存下标而不是次数。 本题要求个数，同一个前缀和出现多次都要贡献答案。
误区：忘记初始化 count[0]=1。 从数组开头开始的合法子数组会漏掉。
误区：atMost 没处理 goal < 0。 当目标为 0 时，需要计算 atMost(-1)，应返回 0。
追问：两种方法怎么选？ 前缀和更通用，滑动窗口依赖非负数组。
追问：为什么 right-left+1 是至多 K 的贡献？ 合法窗口内所有以 right 结尾的后缀都满足和不超过 K。

这些问题能看出你是否理解“恰好”和“至多”的转换。

七、加强记忆

二进制数组和为 S 有两条路：前缀和哈希直接数 sum-goal 出现次数；或者利用非负性，做 atMost(goal)-atMost(goal-1)。前者记“个数存次数”，后者记“恰好等于 = 至多相减”。面试中先讲前缀和，再补充滑动窗口优化，会显得思路很完整。

简化版

详细版