和为 K 的子数组
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
速度
题目描述
给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的连续子数组的个数。
示例 1
输入：nums = [1,1,1], k = 2
输出：2
示例 2
输入：nums = [1,2,3], k = 3
输出：2
模拟答题者思考
1. 我先写暴力：枚举 (l,r)，算 sum(l..r) 是否为 k，O(n²)。
2. 重复在哪里？每个 r 都在重复找「哪些 l 可行」。
3. 我想把「找 l」变成查表：pre[r] - pre[l-1] = k → pre[l-1] = pre[r] - k。
4. 所以扫到 r 时，只要知道历史上 pre[r]-k 出现几次即可。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
pre | int | 定义：扫到当前位置的前缀和 维护：每轮后 pre = sum(nums[0..i]) 更新：当扫过 nums[i] 时，pre += nums[i] |
cnt[s] | map<int,int> | 定义：历史上前缀和为 s 的出现次数 维护：每轮后 cnt 中 pre 的计数已加 1 更新：统计完 ans 后 cnt[pre]++ |
ans | int | 定义：和为 k 的连续子数组个数 维护：累计所有满足 pre[r] - pre[l-1] = k 的 (l,r) 对数 更新：每轮 ans += cnt[pre - k] |
落码步骤
1. cnt[0] = 1 （空前缀，对应左端点在 index=0 之前）
2. 遍历 nums，更新 pre += nums[i]
3. ans += cnt[pre - k] （查历史中有多少合法左端点）
4. cnt[pre]++ （将当前前缀和记入历史，必须在统计 ans 之后）
代码实现
class Solution:
def subarraySum(self, nums: list[int], k: int) -> int:
# cnt[s]：历史上前缀和等于 s 的出现次数
cnt = {0: 1} # 空前缀 pre=0 已出现 1 次
pre = 0 # 扫到当前位置的前缀和
ans = 0 # 和为 k 的连续子数组个数
for x in nums:
pre += x
# pre[r] - pre[l-1] = k => 查 pre-k 历史出现几次
ans += cnt.get(pre - k, 0)
# 必须把当前 pre 记入历史；若先 cnt[pre]++ 再统计，会多算含当前点的子数组
cnt[pre] = cnt.get(pre, 0) + 1
return ansclass Solution {
public:
int subarraySum(vector& nums, int k) {
// cnt[s]：历史上前缀和等于 s 的出现次数
unordered_map cnt;
// 空前缀 pre=0 已出现 1 次，对应左端点在 index 0 之前的子数组
cnt[0] = 1;
int pre = 0; // 扫到当前位置的前缀和
int ans = 0; // 和为 k 的连续子数组个数
for (int x : nums) {
pre += x;
// pre[r] - pre[l-1] = k => pre[l-1] = pre - k
// 查历史上 pre-k 出现几次，即有多少个合法左端点
ans += cnt[pre - k];
// 必须把当前 pre 记入历史；若先 cnt[pre]++ 再统计，会多算含当前点的子数组
cnt[pre]++;
}
return ans;
}
};
// 时间 O(n)，空间 O(n) 复杂度分析
时间复杂度
O(n)
空间复杂度
O(n)
常见坑
顺序错误：必须先 ans += cnt[pre-k]，再 cnt[pre]++，否则会把当前点也算进去。
忘记 cnt[0]=1：空前缀的计数至关重要，否则从 index=0 开始的合法子数组会被漏掉。
把「连续子数组」误当「组合求和」：本题是统计连续段的个数，不需要回溯或 DP。
必测边界 Case
Case 1：k=0 且有零元素
nums = [0,0,0], k = 0 → 输出 6（空前缀 + 各种组合）
Case 2：全部元素都是正数但和为 k
nums = [1,2,3], k = 6 → 输出 1（[1,2,3]）
Case 3：单元素数组
nums = [5], k = 5 → 输出 1