5.2 KiB
tags, create time
| tags | create time | ||||
|---|---|---|---|---|---|
|
2026-05-14 10:00 |
10-和为 K 的子数组
题面
LeetCode 560. Subarray Sum Equals K
给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的子数组的个数。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
提示：
1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7
思路
[!question] 💡 思考 如果只要求「子数组和」，最朴素的做法是什么？两层循环枚举左右端点，内层求和——时间复杂度 O(n³)，优化一下可以累加做到 O(n²)。但 n ≤ 2×10⁴，O(n²) 会超时。如何降到 O(n)？
关键概念：前缀和（Prefix Sum）
定义 prefixSum[i] 为 nums[0] ~ nums[i-1] 的和（即前 i 个元素的前缀和），特别地，prefixSum[0] = 0。
那么任意子数组 nums[i..j] 的和就可以用公式表示：
nums[i..j] 的和 = prefixSum[j+1] - prefixSum[i]
[!note] 🤔 想一想 为什么这个公式成立？想象你有两桶水：一桶装了前 j+1 瓶，另一桶装了前 i 瓶。倒掉小桶里的水，剩下的不正好是大桶中第 i 到 j 瓶水的总量吗？
核心转化
我们希望找到所有满足条件的 (i, j) 对：
prefixSum[j+1] - prefixSum[i] == k
等价变形后得到：
prefixSum[i] == prefixSum[j+1] - k
翻译成人话： 当我遍历到位置 j 时，已经知道了当前的前缀和 sum，我只需要回头看之前有多少次出现过 sum - k——每出现一次，就对应一个和为 k 的子数组。
方法：前缀和 + 哈希表 ⭐（O(n)）
用一个哈希表记录每个前缀和出现的次数，一边遍历一边查询和更新。
**流程：**初始化 sum = 0, count = 0, mp = {0: 1} → 遍历累加 sum → 查 mp[sum-k] 加到计数 → 记录 mp[sum]++ → 返回 count
以 nums = [1, 2, 3], k = 3 为例，逐步跟踪：
| 步骤 | i | nums[i] | 当前 sum | sum - k | mp 中 sum-k 的次数 | count | mp 状态 |
|---|---|---|---|---|---|---|---|
| 初始 | - | - | 0 | - | - | 0 | {0: 1} |
| 1 | 0 | 1 | 1 | -2 | 0 | 0 | {0:1, 1:1} |
| 2 | 1 | 2 | 3 | 0 | 1 | 1 | {0:1, 1:1, 3:1} |
| 3 | 2 | 3 | 6 | 3 | 1 | 2 | {0:1, 1:1, 3:1, 6:1} |
最终结果：2。对应的两个子数组分别是 [1, 2] 和 [3]。
[!question] 💡 为什么哈希表要初始化为
{0: 1}？因为「从索引 0 开始的某个前缀恰好等于 k」也是一种合法情况。当
sum == k时，sum - k = 0，我们需要在 mp 中找到0出现了一次——这代表存在一个从起始位置开始的子数组满足条件。
为什么用哈希表而不是其他结构？
- 题目中元素有负数，前缀和不是单调的 → 不能用双指针或二分
- 只需要「快速查找某个值出现的次数」→ 哈希表均摊 O(1)
- 可以在一次遍历中完成 → 不需要额外预处理
技巧
[!tip] 🔑 核心模式：前缀和 + 哈希表
当题目中出现「连续子数组」「区间和」等关键词，且数组包含负数时，优先考虑前缀和。如果需要找特定值的组合，将前缀和映射关系存入哈希表即可在 O(n) 内解决。
常见变体：
- 「和为 K 的最长子数组」— mp 存的是「第一次出现该前缀和的位置」，而非次数
- 「被 K 整除的子数组」— 查
sum % K是否相同（注意处理负数取模）- 「不超过 K 的最大子数组和」— 需要结合有序集合（TreeSet / std::set）
[!note] 🐹 Go 中的细节
- Go 的
map访问不存在的 key 时返回零值（int 类型为 0），所以mp[sum-k]天然安全，不会 panicmp[sum]++简洁地完成了「不存在则插入值为 1，存在则 +1」两个操作
[!info] 📊 复杂度分析
- 时间：O(n)，仅一次线性扫描，每次哈希表操作均摊 O(1)
- 空间：O(n)，哈希表最多存储 n+1 个不同的前缀和
[!warning] ⚠️ 与前缀和+二维数组的区别
本题是一维版本。如果是二维矩阵中的子矩阵求和问题（如 LeetCode 363），思路仍然是前缀和，但需要配合「压缩行」技巧降维到一维来处理。
代码
func subarraySum(nums []int, k int) int {
// mp 记录每个前缀和出现的次数
mp := make(map[int]int) // 数值 -> 出现次数的映射
mp[0] = 1 // 前缀和为 0 出现过一次（空前缀）
sum := 0 // 当前前缀和
count := 0
for _, num := range nums {
sum += num
// 如果之前出现过 sum-k，说明存在若干子数组和为 k
count += mp[sum-k]
// 记录当前前缀和
mp[sum]++
}
return count
}
[!success] ✅ 运行验证
这是 LeetCode 第 560 题，通过率约 47%。作为「前缀和 + 哈希表」的经典入门题，掌握了这个范式后可以轻松应对更多区间和相关的变体问题。
运行时间：0 ms（Go），空间消耗：7.3 MB，均优于绝大多数提交。