560. 和为 K 的子数组（Subarray Sum Equals K）

频次 ★★★★ · 难度 🟡 · 高频：字节/美团

题目

给定一个整数数组和一个整数 k，找到和为 k 的连续子数组的个数。

示例：

输入: nums = [1, 1, 1], k = 2
输出: 2
解释: [1,1] 出现两次（索引 [0,1] 和 [1,2]）

思路

前缀和 + HashMap：

• prefixSum[i] 表示 nums[0..i-1] 的和
• 子数组 nums[j..i] 的和 = prefixSum[i+1] - prefixSum[j]
• 要找 prefixSum[i+1] - prefixSum[j] = k，即 prefixSum[j] = prefixSum[i+1] - k
• 用 HashMap 记录每个前缀和出现的次数

初始化 map.put(0, 1) 处理从索引 0 开始的子数组。

代码

public int subarraySum(int[] nums, int k) {
    int count = 0, prefixSum = 0;
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    for (int num : nums) {
        prefixSum += num;
        count += map.getOrDefault(prefixSum - k, 0);
        map.put(prefixSum, map.getOrDefault(prefixSum, 0) + 1);
    }
    return count;
}

复杂度

• 时间：O(n) — 一次遍历
• 空间：O(n) — HashMap 最多存 n 个前缀和

边界条件

• map.put(0, 1) 的初始化不能省略：这代表”前缀和为 0 出现过一次”，用于处理”从数组开头就直接构成和为 k 的子数组”的情况（比如 nums=[1,2,3], k=3，前两个数之和 3 出现在 nums[0..1]，需要靠这个初始映射才能被计数）。
• 数组含负数：前缀和不再单调，无法用滑动窗口（滑动窗口要求”扩大窗口和只增不减”），必须用前缀和 + HashMap 的方法。
• k == 0：统计的是”和为 0 的子数组个数”，算法不需要特殊处理，逻辑天然覆盖。

变式

• 如果数组全为正数：前缀和单调递增，可以退化成滑动窗口（双指针），不需要 HashMap，空间从 O(n) 降到 O(1)——这是本题的一个重要追问方向。
• 只需要判断”是否存在”满足条件的子数组，而不是计数：逻辑几乎一样，找到 map.containsKey(prefixSum - k) 时直接返回 true 即可，不需要维护计数。
• 求最长的和为 k 的子数组长度：HashMap 里存”前缀和第一次出现的下标”而不是”出现次数”（因为要最长，只关心最早出现的位置）。

易错点

• 一定要先用 count += map.getOrDefault(...) 累加答案，再把当前前缀和存入/更新 map，顺序反了会把”子数组长度为 0”的情况错误计入（用当前前缀和自己匹配自己）。
• 前缀和数组本身不需要真的建出来，用一个滚动变量 prefixSum 累加即可，建完整数组是不必要的额外空间。

面试追问

• 为什么数组含负数时不能用滑动窗口？ 滑动窗口依赖”窗口扩大时和单调增大、窗口缩小时和单调减小”这个性质来决定何时移动左右指针；一旦有负数，扩大窗口和也可能减小，无法判断该移动哪个指针，因此必须退化到更通用但空间开销更大的前缀和+哈希方法。
• map.put(0, 1) 具体解决了什么问题，能举例说明吗？ 举例 nums = [3, 4, 7, 2, -3, 1, 4, 2], k = 7：nums[0..2] = 3+4+7 = 14… 更直接的例子是 nums = [1,2,3], k = 3，遍历到下标 1（nums[0..1]，前缀和为 3）时，需要查找 prefixSum - k = 0，如果没有预先在 map 里放入 (0,1)，这个”从头开始恰好等于 k”的子数组就无法被计数到。

关联题

• 同套路：1. 两数之和 —— 前缀和数组上的”两数之差”，哈希查补数同款
• 进阶：525. 连续数组、974. 和可被 K 整除的子数组 —— 前缀和 + 哈希的变体
• 易混：53. 最大子数组和 —— 同为子数组：求最值用 Kadane，求计数用前缀和哈希；本题有负数，滑动窗口不适用
• 知识点：前缀和专题见前缀和与差分