158 lines
5.2 KiB
Markdown
158 lines
5.2 KiB
Markdown
---
|
||
tags: ["LeetCode", "前缀和", "哈希表", "中等"]
|
||
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]` 天然安全，不会 panic
|
||
> - `mp[sum]++` 简洁地完成了「不存在则插入值为 1，存在则 +1」两个操作
|
||
|
||
> [!info] 📊 复杂度分析
|
||
>
|
||
> - 时间：O(n)，仅一次线性扫描，每次哈希表操作均摊 O(1)
|
||
> - 空间：O(n)，哈希表最多存储 n+1 个不同的前缀和
|
||
|
||
> [!warning] ⚠️ 与前缀和+二维数组的区别
|
||
>
|
||
> 本题是一维版本。如果是二维矩阵中的子矩阵求和问题（如 LeetCode 363），思路仍然是前缀和，但需要配合「压缩行」技巧降维到一维来处理。
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
```go
|
||
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，均优于绝大多数提交。
|