Leetcode Hot 100 继续推进，这回轮到前缀和家族的一位招牌选手：和为 K 的子数组。
这题看着像是在数子数组， 实际上考的是一手很标准的组合拳：
- 前缀和 负责把“区间和”变成“两个前缀和之差”
- 哈希表 负责把“找历史答案”这件事压到
O(1)
一句话概括它的灵魂：
枚举右端点，回头查有多少个前缀和刚好能和当前凑出
k。
题目链接
题目描述
给你一个整数数组 nums 和一个整数 k，请你统计并返回 和为 k 的连续子数组 的个数。
这里的子数组必须是连续的。
解题思路：前缀和 + 哈希表
这题如果暴力做，最直观的想法是枚举所有子数组：
- 固定起点
- 固定终点
- 计算区间和
这样时间复杂度很容易来到 O(n^2)，甚至更高。
但如果我们把区间和换个表达方式，事情就顺了。
前缀和是什么？
设当前遍历到某个位置时，前缀和为：
presum = nums[0] + nums[1] + ... + nums[i]如果之前某个位置的前缀和是 old_sum，
那么这两者之间那一段连续子数组的和就是：
presum - old_sum而题目要求这段子数组和等于 k，于是就有：
presum - old_sum = k移项后得到：
old_sum = presum - k这句话非常关键：
当我们遍历到当前位置时，只要之前出现过前缀和
presum - k，就说明存在若干个以当前位置结尾的子数组，它们的和等于k。
为什么要用哈希表
问题到这里就变成了：
当前前缀和是
presum，之前有多少个前缀和等于presum - k？
这时候哈希表就登场了。
我们用一个字典 record 来记录：
- 某个前缀和出现了多少次
遍历数组时，每到一个新位置：
- 更新当前前缀和
presum - 查
record[presum - k] - 把查到的次数加进答案
- 再把当前前缀和记进
record
这一套下来，整题只需要一趟遍历。
代码实现
from collections import defaultdict
class Solution(object): def subarraySum(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ record = defaultdict(int) record[0] = 1
ans = 0 presum = 0
for num in nums: presum += num ans += record[presum - k] record[presum] += 1
return ans代码拆解
1. 初始化哈希表
record = defaultdict(int)record[0] = 1这里的 record[0] = 1 是整题最容易被忽略、但又特别关键的一步。
它表示：
在还没开始遍历数组之前，前缀和
0已经出现过 1 次。
为什么要这样做？
因为如果某一段子数组恰好是从下标 0 开始，到当前位置结束，
它的和也应该被统计进去。
举个小例子：
nums = [1, 2]k = 3当遍历到第二个元素时：
presum = 3presum - k = 0如果哈希表里提前放了一个 0: 1，
那么这段从开头开始的子数组 [1, 2] 就能被正确计入答案。
2. 更新当前前缀和
presum += num我们一边遍历，一边维护从数组开头到当前位置的累积和。
3. 查找历史前缀和
ans += record[presum - k]这一步是核心中的核心。
它的含义是：
- 当前前缀和是
presum - 如果以前出现过前缀和
presum - k - 那么从那个位置之后到当前位置这一段，和就等于
k
而且注意：
- 不是只找一个
- 是找 出现过几次
因为同一个前缀和可能出现多次， 每出现一次，就对应一个合法子数组。
4. 记录当前前缀和
record[presum] += 1把当前前缀和加入哈希表，供后面的元素继续使用。
这里顺序不能写反。
一定要先统计：
ans += record[presum - k]再记录：
record[presum] += 1否则就可能把当前这个位置错误地拿去匹配自己，导致答案出锅。
示例推演
假设输入：
nums = [1, 1, 1]k = 2初始化：
record = {0: 1}presum = 0ans = 0第一轮：遍历到第一个 1
presum = 1presum - k = -1哈希表里没有 -1，所以当前没有新答案。
然后记录：
record = {0: 1, 1: 1}第二轮：遍历到第二个 1
presum = 2presum - k = 0哈希表里 0 出现了 1 次，说明有 1 个子数组和为 2。
于是：
ans = 1再记录当前前缀和：
record = {0: 1, 1: 1, 2: 1}第三轮：遍历到第三个 1
presum = 3presum - k = 1哈希表里 1 出现了 1 次，说明又找到 1 个子数组。
于是：
ans = 2最终答案为：
2对应的两个子数组分别是：
[1, 1]（下标0 ~ 1）[1, 1]（下标1 ~ 2）
为什么这题不能直接用双指针
有些同学会想：
连续子数组求和，能不能滑动窗口、双指针直接做？
这题通常不行。
因为数组里可能有：
- 正数
- 负数
- 0
一旦有负数，窗口和就不再具备单调性， 你没法保证“窗口变大就更大，窗口变小就更小”。
所以滑动窗口在这里容易失效， 前缀和 + 哈希表才是正解。
复杂度分析
时间复杂度
整段代码只遍历一次数组，
哈希表查找和插入平均都是 O(1)。
所以时间复杂度为：
O(n)空间复杂度
哈希表最多存下 n 个不同的前缀和，
所以空间复杂度为：
O(n)易错点总结
1. 忘记写 record[0] = 1
这个一忘，从下标 0 开始的合法子数组就统计不到。
2. 哈希表更新顺序写反
正确顺序是：
ans += record[presum - k]record[presum] += 1先查，再记。
3. 误以为能用滑动窗口
如果题目没有保证数组元素全为正数， 那滑动窗口就别乱冲，容易当场翻车。
小结
这题的核心其实就一句：
区间和等于
k，等价于“两个前缀和的差等于k”。
所以我们可以：
- 一边遍历数组
- 一边维护当前前缀和
- 一边用哈希表统计历史前缀和出现次数
最终把原本容易写成 O(n^2) 的题，压到 O(n)。
Hot 100 刷到这里，前缀和这把刀算是正式开锋了。 记住这题，后面很多“连续子数组求和”的题，换个皮还是它表兄弟。🦐