最长和为 K 的子数组怎么用前缀和加哈希表？

简化版

最长和为 K 的子数组可以用前缀和。

当前位置前缀和为 sum，如果之前出现过 sum - k，那么中间这段子数组和就是 k。

为了长度最长，哈希表要记录每个前缀和第一次出现的位置，不要覆盖。

详细版

设 prefix[j] - prefix[i] = k，那么 prefix[i] = prefix[j] - k。

遍历数组时维护当前前缀和 sum。如果 sum - k 在哈希表中，说明从该位置后一个元素到当前下标的和为 k，可以更新最大长度。

哈希表初始化 0 -> -1，表示从数组开头开始的子数组。

记录前缀和位置时，只记录第一次出现，因为越早的位置能形成越长的区间。

时间复杂度 O(n)，空间复杂度 O(n)。

完整版教学

一、为什么不能简单用滑动窗口

如果数组全是正数，子数组和随着右扩会增大，左缩会减小，可以用滑动窗口。但这题通常允许负数，窗口和没有单调性。右扩加入负数可能让和变小，左缩移出负数可能让和变大，双指针无法稳定判断方向。

易错点：有负数的子数组和问题，优先想前缀和 + 哈希，而不是滑动窗口。

二、公式怎么推出来

区间 (i, j] 的和等于：

prefix[j] - prefix[i]

如果这段和要等于 k，则：

prefix[i] = prefix[j] - k

遍历到 j 时，prefix[j] 已知，只要查一下之前有没有 prefix[j] - k，就能知道是否存在以当前位置结尾的合法子数组。

三、为什么保存第一次出现

题目要最长长度。当前位置 j 固定时，左边界越靠前，长度越大。因此某个前缀和第一次出现的位置最有价值。后续如果再次出现同样前缀和，覆盖掉第一次位置，可能会让答案变短。

前缀和	第一次位置	后来位置	用哪个更长
3	1	5	第一次位置
-2	0	4	第一次位置

所以写代码时要用 if (!map.has(sum)) map.set(sum, i)。

四、带数字推演

数组 [1,-1,5,-2,3]，k = 3。

初始 sum=0 at -1
i=0 sum=1，找 -2，没有，记录 1
i=1 sum=0，找 -3，没有，0 已存在不覆盖
i=2 sum=5，找 2，没有，记录 5
i=3 sum=3，找 0，在 -1，长度 4
i=4 sum=6，找 3，在 3，长度 1

最长长度是 4，对应 [1,-1,5,-2]。

五、代码模板

实现如下：

function maxSubArrayLen(nums, k) {
  const firstIndex = new Map()
  firstIndex.set(0, -1)
  let sum = 0
  let ans = 0
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i]
    if (firstIndex.has(sum - k)) {
      ans = Math.max(ans, i - firstIndex.get(sum - k))
    }
    if (!firstIndex.has(sum)) {
      firstIndex.set(sum, i)
    }
  }
  return ans
}

这个模板和“和为 K 的子数组个数”很像，但一个存次数，一个存最早下标。

六、常见误区与追问

误区：遇到相同前缀和就覆盖。 求最长时应保留最早位置。
误区：把计数题模板直接搬过来。 计数题存出现次数，最长长度题存最早下标。
误区：有负数还用滑动窗口。 负数破坏窗口和单调性，移动方向不可靠。
追问：初始化 0 -> -1 有什么用？ 让从下标 0 开始、和为 K 的子数组能被计算。
追问：如果要求最短和为 K 呢？ 可能需要保存更靠后的位置或用其他结构，目标不同，哈希策略也不同。

这些追问重点是“哈希表里到底存什么”。

七、加强记忆

最长和为 K 记成“当前 sum 找 sum-k，位置存最早”。前缀和公式给出合法区间，哈希表负责快速找左端前缀。因为要最长，同一个前缀和只记录第一次出现；因为可能从开头开始，提前放入 0 -> -1。遇到负数时，这个模板比滑动窗口稳。

简化版

详细版