和为K的子数组：前缀和+哈希的黄金组合

老张2026/4/30大约 10 分钟

和为K的子数组：前缀和+哈希的黄金组合

适读人群：Java 开发者、准备算法面试的工程师 | 阅读时长：约20分钟 | 难度：Medium

开篇故事

两年前我在做一个用户行为分析系统，有个需求：给定一段时间内每个用户的行为评分序列，找出所有"连续时间段内行为评分之和等于阈值 k"的片段数量，用来判断用户是否存在异常行为集中期。

我最初的实现是双层循环枚举所有子数组，O(n²) 的复杂度。对于用户量大的场景，这段代码每天跑批处理要将近一个小时。后来我想起了 LeetCode 560 这道题——和为 K 的子数组，这不就是我面对的问题吗？

把前缀和+哈希表的方案引入之后，同样的计算从一个小时降到了不到两分钟。这是这道题给我印象最深的一次应用。

前缀和是数组类问题里用途最广的预处理技巧，哈希表是查找加速的万能工具。把这两者结合在一起，能解决一大类"子数组和等于某个值"的问题。搞清楚这道题，后面一整个专题都会豁然开朗。

一、题目解析

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

给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的子数组的数目。

子数组是数组中元素的连续非空序列。

输入输出示例：

示例 1（基础情况）：

输入：nums = [1,1,1], k = 2
输出：2
解释：[1,1] 出现两次（下标 [0,1] 和 [1,2]），都满足

示例 2（负数元素）：

输入：nums = [1,2,3], k = 3
输出：2
解释：[1,2] 和 [3] 都满足

边界情况 3（包含负数）：

输入：nums = [-1,-1,1], k = 0
输出：1
解释：[-1,-1,1] 和等于 -1，[1] 和等于 1，不满足，只有整个数组不对，等等...
     实际检查：[-1,-1]=−2不满足，[-1,1]=0满足，所以输出 1

边界情况 4（k=0，元素有正有负）：

输入：nums = [1,-1,1,-1], k = 0
输出：4
解释：[1,-1], [-1,1], [1,-1,1,-1], [-1,1,-1] 共4个，注意单个元素和不是0

边界情况 5（单个元素等于 k）：

输入：nums = [5], k = 5
输出：1

考察的核心知识点：

前缀和的定义与计算
"和为 k 的子数组" 转化为 "两个前缀和之差等于 k"
哈希表记录前缀和出现次数
为什么不能用滑动窗口（有负数时窗口单调性失效）

二、解法一：暴力解法

思路分析

枚举所有子数组，计算每个子数组的和，统计等于 k 的数量。

两层循环：外层枚举起点 i，内层枚举终点 j，同时累加从 i 到 j 的和（不需要每次重新从头加，直接在外层固定 i 时递增求和）。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int sum = 0;
            // 从 i 开始向右扩展，枚举所有以 i 为起点的子数组
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

时间复杂度：O(n²)。

空间复杂度：O(1)。

缺陷： 在 LeetCode 的大测试用例上会 TLE。n=2×10⁴ 时，O(n²) = 4×10⁸，基本就在超时边界了。

三、解法二：为什么滑动窗口不行

在尝试优化之前，很多人会先想到滑动窗口（LeetCode 3、76 都用过）。但这道题不能用滑动窗口，原因在于：

滑动窗口能工作的前提是"窗口和的单调性"：扩展右边界，和增大；收缩左边界，和减小。这样双指针才有方向性。

但这道题的 nums 中包含负数。扩展右边界时，如果加入的是负数，窗口和反而变小了。单调性失效，双指针无法确定何时扩何时缩。

所以这道题需要一个不依赖单调性的方法。

四、解法三：前缀和+哈希（工业级最优解）

核心洞见

前缀和的定义： prefix[i] = nums[0] + nums[1] + ... + nums[i-1]（前 i 个元素之和，prefix[0] = 0）。

子数组和的转化： 子数组 nums[i..j] 的和 = prefix[j+1] - prefix[i]。

要找和为 k 的子数组，就是要找所有满足 prefix[j+1] - prefix[i] == k 的 (i, j) 对，即 prefix[i] == prefix[j+1] - k。

用哈希加速： 遍历数组，维护当前前缀和 curSum。对每个位置 j+1，问题转化为：在已经遍历过的前缀和中，有多少个 curSum - k？用哈希表记录每个前缀和出现的次数，O(1) 查询。

关键点：哈希表初始存入 {0: 1}，表示前缀和为 0 出现了 1 次（对应空前缀，即子数组从下标 0 开始的情况）。

算法流程

完整 Java 代码

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int subarraySum(int[] nums, int k) {
        // key: 前缀和的值, value: 该前缀和出现的次数
        Map<Integer, Integer> prefixCount = new HashMap<>();
        // 初始化：前缀和为 0 出现 1 次（空前缀）
        // 这个初始化非常重要，用来处理"子数组从下标 0 开始"的情况
        prefixCount.put(0, 1);
        
        int curSum = 0;  // 当前前缀和
        int count = 0;
        
        for (int num : nums) {
            curSum += num;  // 更新当前前缀和
            
            // 查找之前有多少个前缀和等于 curSum - k
            // 如果存在，说明这些前缀和到当前位置的子数组和等于 k
            int complement = curSum - k;
            count += prefixCount.getOrDefault(complement, 0);
            
            // 将当前前缀和加入哈希表
            prefixCount.merge(curSum, 1, Integer::sum);
        }
        
        return count;
    }
}

复杂度分析

时间复杂度：O(n)

只有一层 for 循环，每次循环做 O(1) 的 HashMap 操作。整体 O(n)。

空间复杂度：O(n)

HashMap 最坏存 n 个不同的前缀和。

我在 LeetCode 提交这个版本，运行时间 14ms，击败 96.8% 的 Java 用户。和暴力解法在大用例上的超时相比，这是质的飞跃。

五、举一反三

前缀和+哈希模板

// 通用模板：统计满足 prefix[j] - prefix[i] == target 的对数
Map<Integer, Integer> prefixCount = new HashMap<>();
prefixCount.put(0, 1);  // 空前缀初始化（关键！）
int curSum = 0;
int count = 0;

for (int num : nums) {
    curSum += num;
    count += prefixCount.getOrDefault(curSum - target, 0);
    prefixCount.merge(curSum, 1, Integer::sum);
}
return count;

面试中的变体和追问

为什么要初始化 prefixCount.put(0, 1)？ 答：当 curSum == k 时，我们需要查找前缀和为 curSum - k = 0 出现的次数。如果没有这个初始化，以下标 0 开始、和为 k 的子数组会被漏掉。初始化 {0: 1} 就是说"存在一个空前缀，其和为 0"。
这道题能不能用滑动窗口？ 答：不能。数组中可能有负数，窗口和不具有单调性，无法确定何时扩展何时收缩。
如果要找最长的和为 k 的子数组（不是统计数量）怎么做？ 答：哈希表存前缀和第一次出现的下标（而不是次数），遍历时查找 curSum - k 是否存在，用 当前下标 - 存储的下标 计算长度，取最大值。注意哈希表只存第一次出现的下标，不更新，因为我们要最长的子数组。

六、踩坑实录

坑一：忘记初始化 `{0: 1}`

现象： 输入 nums = [1,2,3], k = 3，期望输出 2（[1,2] 和 [3]），代码只返回 1（漏掉了 [3]）。

原因： 没有初始化 prefixCount.put(0, 1)。当遍历到 nums[2]=3，curSum=6，查找 6-3=3 时，表里有 prefix=3（遍历 [1,2] 后），找到了 [1,2,3] 不对——等等，这里我们要找和为3的，从 prefix=3 到 prefix=6 是第三个元素 3，和就是 3。

让我重新分析：[3] 对应的是 prefix[3] - prefix[2] = 6 - 3 = 3 = k，这在遍历到 i=2（nums[2]=3）时，查找 curSum-k=6-3=3，表里此时有 {0:1, 1:1, 3:1}（前缀和分别是0,1,3），所以找到了 3，count++。这是正确的。

[1,2] 对应 prefix[2] - prefix[0] = 3 - 0 = 3 = k，在遍历到 i=1（nums[1]=2）时，curSum=3，查找 curSum-k=0，如果没有初始化 {0:1}，找不到 0，漏掉了 [1,2]。

解法： 初始化 prefixCount.put(0, 1) 是前缀和哈希这个模板里最重要的一步，绝对不能省。

坑二：同一个前缀和只记录一次（适用于找最长子数组时）

现象： 在"找最长和为 k 的子数组"变种题里，用了 merge 更新了前缀和的次数，但实际需要的是"第一次出现的下标"。

原因： 两个问题的哈希表用途不同：

统计数量：哈希表存 {前缀和: 出现次数}，用 merge/+1 更新
找最长子数组：哈希表存 {前缀和: 第一次出现的下标}，只存不更新（保留最早的下标，使子数组尽可能长）

// 找最长和为 k 的子数组
Map<Integer, Integer> firstOccurrence = new HashMap<>();
firstOccurrence.put(0, -1);  // 空前缀下标为 -1
int curSum = 0, maxLen = 0;
for (int i = 0; i < nums.length; i++) {
    curSum += nums[i];
    if (firstOccurrence.containsKey(curSum - k)) {
        maxLen = Math.max(maxLen, i - firstOccurrence.get(curSum - k));
    }
    // 只在不存在时才存入，保留第一次出现的下标
    firstOccurrence.putIfAbsent(curSum, i);
}

坑三：负数前缀和导致的哈希冲突误解

现象： 有负数时担心前缀和出现负值，以为哈希表不能处理。

原因： 误解。HashMap 的 key 可以是任何 Integer，包括负数。前缀和可以是负数、零、正数，都能正确存入哈希表并查找。这道题完全不需要特殊处理负数前缀和。

七、总结

这道题把"前缀和"和"哈希查找"这两个独立的工具组合在了一起，产生了 1+1>2 的效果。单独的前缀和需要 O(n²) 遍历所有对，单独的哈希查找不知道要查什么，但两者结合，把"找两个前缀和之差等于 k"降到了 O(n)。

三条核心要点：

子数组和问题的核心转化：sum(i..j) == k ⟺ prefix[j+1] - prefix[i] == k ⟺ prefix[i] == prefix[j+1] - k。这个转化是所有前缀和哈希题的基础。
初始化 {0: 1} 必不可少，它处理了子数组从下标 0 开始（即空前缀）的情况。
有负数时，滑动窗口失效，必须用前缀和+哈希。这是本题和"无负数"版本（如最大子数组和=k）的本质区别。

延伸思考：

前缀和+哈希的这个模式，其实可以看作是一种"时间轴上的信息积累"：我们从左到右遍历，边走边把历史信息存入哈希表，遇到新情况时查历史。这种模式和两数之和（遍历过程中查哈希表找补数）本质上是同一个思路，只是应用场景不同。