算法面试突击手册 —— 前缀和
一、概念与特点
大白话 + 类比
前缀和 = 高速路上的里程碑
你在高速路上开车，想知道从 A 出口到 B 出口有多远。你不会每次拿出尺子量整段路，而是看里程碑：B 里程碑 - A 里程碑 = 距离。前缀和就是那条路上的里程碑数组：
preSum[i]表示从起点到第 i 个位置的累计值。核心公式：
区间[i, j]的和 = preSum[j+1] - preSum[i]。把 O(n) 的区间求和变成 O(1) 的两数相减。
前缀和 + HashMap 是超级组合：把”前缀和”作为 key 存入 HashMap，遍历时在 O(1) 时间内回答”之前某个前缀和出现过几次”，从而统计符合条件的子数组数量。这是 560 题的核心思想。
核心特征（什么时候该想到用它）
| 特征 | 说明 |
|---|---|
| 频繁查询区间和 | 多次问不同区间 [i,j] 的和，预处理前缀和 O(1) 回答 |
| 和为 K 的子数组计数 | 统计有多少连续子数组和为 K |
| 前缀积 × 后缀积 | 不一定是”和”，乘积、异或等同理 |
| 树上的路径和 | 二叉树中某条下载路径的和 = 前缀和的差 |
| O(n) 的超时替代方案 | 暴力子数组枚举 O(n²)，前缀和 + HashMap 降到 O(n) |
识别信号词
- “子数组之和”、“和为 K” → 前缀和 + HashMap
- “连续子数组” + 求和条件 → 前缀和
- “除自身以外的乘积” → 前缀积 × 后缀积（238 题）
- “树中路径和为 target”、“任意起点终点” → 树上前缀和（437 题）
- “O(n) 时间” + 子数组求和 → 前缀和是唯一选择
容易混淆的区分
| 问题类型 | 方法 | 代表题 |
|---|---|---|
| 求区间和（一次查询） | 直接遍历 O(n) | — |
| 求区间和（多次查询） | 前缀和数组 O(1) 每次 | 303 |
| 统计和为 K 的子数组个数 | 前缀和 + HashMap | 560 |
| 求最长和为 K 的子数组 | 前缀和 + HashMap（存首次位置） | 525 |
| 树上的路径和 | 树上前缀和 + HashMap + 回溯 | 437 |
二、应用场景
核心公式与模板
核心公式：区间 [i, j] 的和 = preSum[j+1] - preSum[i]
标准前缀和数组（下标从 1 开始）：
preSum[0] = 0
preSum[k] = nums[0] + nums[1] + ... + nums[k-1]
示例：nums = [3, 5, 2, -1, 4]
preSum = [0, 3, 8, 10, 9, 13]
求 nums[1..3] 的和 → preSum[4] - preSum[1] = 9 - 3 = 6
(等同于5 + 2 + (-1) = 6） ✓前缀和 + HashMap 万能模板
// 统计和为 K 的子数组个数 —— 最常用模式
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1); // 必须！处理从 nums[0] 开始就等于 K 的情况
int preSum = 0, count = 0;
for (int num : nums) {
preSum += num;
// 核心：找之前有几个位置的前缀和 = preSum - K
// 这些位置到当前位置之间的子数组和就是 K
count += map.getOrDefault(preSum - K, 0);
map.put(preSum, map.getOrDefault(preSum, 0) + 1);
}为什么 map.put(0, 1) 是必须的
如果子数组从 nums[0] 开头就直接等于 K，那么 preSum - K = 0。如果没有 map.put(0, 1)，getOrDefault(0, 0) 返回 0，这条子数组就被漏掉了。(0, 1) 表示”空前缀和出现了 1 次”，代表从数组起点这个虚拟位置。
三、Hot 100 精讲题目
560. Subarray Sum Equals K 和为 K 的子数组
📌 统计数组中和为 k 的连续子数组的个数。如
nums=[1,1,1], k=2→ 2（[1,1]出现两次，下标[0,1]和[1,2]）
🔍 解题分析
为什么用前缀和 + HashMap
暴力枚举所有子数组 O(n²) → 大数据超时。用前缀和可以将”任意子数组的和”转化为”两个前缀和的差”：
sum(i, j) = preSum[j+1] - preSum[i]- 我们想要
sum(i, j) == k，即preSum[j+1] - preSum[i] == k - 移项：
preSum[i] == preSum[j+1] - k - 翻译成人话：遍历到位置 j 时，回头找之前有几个位置的前缀和等于”当前前缀和 - k”
前缀和配合 HashMap 可以在 O(1) 时间回答”之前某个前缀和出现过几次”，将总复杂度降到 O(n)。
核心思路（步骤化）
- 初始化
HashMap：map.put(0, 1)—— 空前缀和为 0，出现 1 次 - 遍历每个元素
num，更新当前前缀和preSum += num - 在 map 中查
preSum - k出现的次数 → 累加到答案 - 将当前
preSum记录到 map 中 - 遍历结束，返回答案
关键边界条件/易错点
| 易错点 | 说明 |
|---|---|
忘记 map.put(0, 1) | 从数组起点开始的子数组会被漏掉 |
| 先查再存 | 必须先查 map，再 put 当前 preSum。如果先存再查，遇到 k=0 时会把当前位置自己也算进去（长度为 0 的假子数组） |
| preSum 可能为负 | nums 有负数时前缀和不是单调的，但 HashMap 方法完全不受影响 |
类比：你现在里程碑 10km 处，想知道之前有没有一段恰好 3km 的路。回头看在 7km 处出现过几次（即之前有几个前缀和 = 10-3=7）。每出现一次，就意味着从那里到当前位置是一段 3km 的子数组。
✅ 完整 Java 实现
public int subarraySum(int[] nums, int k) {
// key = 前缀和的值, value = 该前缀和出现了几次
Map<Integer, Integer> preSumCount = new HashMap<>();
// 【关键】空前缀和为 0 出现 1 次
// 没有这行，所有从 nums[0] 开始的合法子数组都会被漏掉
preSumCount.put(0, 1);
int preSum = 0; // 当前位置的前缀和
int count = 0; // 最终答案
for (int num : nums) {
preSum += num; // 更新前缀和（相当于里程碑走到当前位置）
// 【核心】找之前有几个前缀和 = preSum - k
// 每个匹配的位置 → 当前位置，就是一段和为 k 的子数组
// 注意：必须先查再存！否则 k=0 时会把空子数组也算上
count += preSumCount.getOrDefault(preSum - k, 0);
// 将当前前缀和存入 map，供后面的位置查找
preSumCount.put(preSum, preSumCount.getOrDefault(preSum, 0) + 1);
}
return count;
}手算验证：nums=[1,2,3], k=3
| i | num | preSum | 查 preSum-k=preSum-3 | map 中出现次数 | count | map 存入后 |
|---|---|---|---|---|---|---|
| 初始 | — | 0 | — | — | 0 | {0:1} |
| 1 | 1 | 1 | -2 | 0 | 0 | {0:1, 1:1} |
| 2 | 2 | 3 | 0 | 1 | 1 ← [1,2] | {0:1, 1:1, 3:1} |
| 3 | 3 | 6 | 3 | 1 | 2 ← [3] | {0:1, 1:1, 3:1, 6:1} |
结果 count=2，正好是子数组 [1,2] 和 [3]。
⏱ 复杂度分析
- 时间复杂度：O(n) —— 每个元素访问一次，HashMap 的 get/put 是 O(1)
- 空间复杂度：O(n) —— 最坏情况每个位置的前缀和都不同，HashMap 存 n 个键值对
💡 记忆口诀
“边走边看里程碑，回头找 preSum-K 的影踪；先查后存别忘了，0 存 1 才能开头”
238. Product of Array Except Self 除自身以外数组的乘积
📌 返回数组 answer，其中
answer[i]= nums 中除nums[i]外所有元素的乘积。不能使用除法，且要求 O(n) 时间。如[1,2,3,4]→[24,12,8,6]
🔍 解题分析
为什么不能用除法
如果可以用除法，直接算出总乘积，每个 answer[i] = total / nums[i] 就完事了。但题目明确禁止除法，原因是：
- 如果 nums[i] = 0，除零错误
- 面试考查的是前缀积/后缀积的思想
为什么用前缀积 × 后缀积
把每个位置想象成一个分界线：answer[i] = (nums[i] 左边所有元素的乘积) × (nums[i] 右边所有元素的乘积)。分别维护前缀积和后缀积，两遍扫描即可。
核心思路（步骤化）
- 第一遍（左→右）：
answer[i]暂时存放nums[0] * nums[1] * ... * nums[i-1]（i 左边所有元素的乘积） - 第二遍（右→左）：用一个变量
suffix反向累积右边的乘积，每步answer[i] *= suffix，然后suffix *= nums[i] - 两遍扫描后，answer[i] = 左前缀积 × 右后缀积 = 除自己外所有元素的乘积
关键边界条件/易错点
| 易错点 | 说明 |
|---|---|
| answer[0] 初始化为 1 | 第一个元素左边没有东西，乘积定义为 1（乘法单位元） |
| suffix 初始化为 1 | 同理，最后一个元素右边没有东西 |
| 数组中有 0 | 解法天然处理 0：如果 nums[i]=0，它的 answer 正确 = 左边乘积 × 右边乘积（非零值）；其他位置会因为乘了 0 变 0 |
| suffix 更新顺序 | 先 answer[i] *= suffix（乘之前累积的右边乘积），再 suffix *= nums[i]（把当前元素纳入右边乘积供下一个使用） |
手算验证：nums = [2, 3, 0, 4]
第一遍后 answer = [1, 2, 6, 0]（0 是因为 6×0=0，它前面确实是 2×3=6）
| i（倒序） | suffix（本轮用） | answer[i] *= suffix | suffix *= nums[i] |
|---|---|---|---|
| 3 | 1 | answer[3] = 0×1 = 0 | 1×4 = 4 |
| 2 | 4 | answer[2] = 6×4 = 24 ← | 4×0 = 0 |
| 1 | 0 | answer[1] = 2×0 = 0 | 0×3 = 0 |
| 0 | 0 | answer[0] = 1×0 = 0 | 0×2 = 0 |
结果 [0, 0, 24, 0]。验证：除 0 外包含 0 乘积一定为 0；除 nums[2]=0 外 2×3×4=24 ✓
✅ 完整 Java 实现
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] answer = new int[n];
// ── 第一遍：左 → 右，answer[i] = nums[0] * ... * nums[i-1] ──
// answer[0] 左边没有元素，乘积为 1
answer[0] = 1;
for (int i = 1; i < n; i++) {
// answer[i-1] 已经是前 i-1 个元素的累积乘积
// 再乘上 nums[i-1]，就是前 i 个元素（不含 i 自身）的乘积
answer[i] = answer[i - 1] * nums[i - 1];
}
// ── 第二遍：右 → 左，乘上右边的累积乘积 ──
int suffix = 1; // 当前元素右边的累积乘积（从最右边开始，右边为空，乘积为 1）
for (int i = n - 1; i >= 0; i--) {
// 先乘（answer[i] 现在是"左乘积"，乘上"右乘积" = 除自己外的总乘积）
answer[i] *= suffix;
// 后更新（把当前元素纳入右边乘积，供下一个元素使用）
suffix *= nums[i];
}
return answer;
}⏱ 复杂度分析
- 时间复杂度：O(n) —— 两次独立遍历，每次 O(n)
- 空间复杂度：O(1) —— 不算返回数组 answer，只用了 suffix 一个额外变量
💡 记忆口诀
“左扫存前缀积，右扫后缀乘回来；左右夹击除自己”
437. Path Sum III 路径总和 III
📌 二叉树中，找出路径和等于 targetSum 的路径数目。路径必须向下（父→子），但不必从根开始，也不必在叶子结束。如
root=[10,5,-3,3,2,null,11,3,-2,null,1], targetSum=8→ 3
🔍 解题分析
为什么用前缀和
这道题的本质是”树上的 560 题”——在树上找”向下连续子路径”和为 target。区别在于：
- 数组是线性的（一维），树是分支的（多路径）
- 在数组上”回头找”是天然的（遍历顺序固定），在树上走完一条路径后要去另一条分支，需要回溯（撤销）
如果我们把从根到当前节点的路径上的前缀和都存入 HashMap，那么当前节点为终点时，“以某个祖先节点为起点的路径和” = 当前前缀和 - 祖先前缀和。问题就变成了 preSum[cur] - preSum[ancestor] == target，即查找 preSum[ancestor] == preSum[cur] - target。
核心思路（步骤化）
- DFS 遍历树，维护从根到当前节点的路径前缀和
currentSum - 在 HashMap 中查
currentSum - target出现过几次，累加到答案 - 将
currentSum存入 HashMap（次数+1） - 递归处理左右子树
- 关键：离开当前节点时，把 currentSum 从 HashMap 中移除（次数-1）——这就是回溯的”擦橡皮”
为什么必须回溯
DFS 走到左子树分支的底部后，会回溯到分叉口再去右子树。如果不擦掉左子树分支上的前缀和记录，右子树分支上的节点在 HashMap 中查找时，会把左子树分支的前缀和也错误地算进来（它们不在从根到当前节点的同一条路径上）。
关键边界条件/易错点
| 易错点 | 说明 |
|---|---|
map.put(0L, 1) | 必须初始化，处理从根节点开始的路径 |
| 必须先查再存 | 否则会把当前节点到自身的路径（长度为 0）也算进去 |
| 回溯时还原 | 离开节点必须 map.put(key, val-1)，否则不同分支互相污染 |
| 前缀和用 Long | 节点值范围可能导致前缀和溢出 int |
| 节点值可能为负 | 即使到某个节点前缀和已经超过 target，也不能停止 DFS，因为后面可能有负数把它拉回来 |
类比：想象从树根往下走，带着一个本子（HashMap）记录”走到每个深度时前缀和是多少”。走到一个节点，翻开本子找”当前前缀和 - target”，看看有几个深度匹配。走到底后原路返回，每退回一步就把本子上对应深度的记录擦掉——就像进入死胡同后原路返回并擦掉墙上的粉笔记号。
✅ 完整 Java 实现
public int pathSum(TreeNode root, int targetSum) {
// key = 前缀和, value = 从根出发该前缀和出现了几次
Map<Long, Integer> preSumCount = new HashMap<>();
// 【关键】空前缀和为 0，出现 1 次（处理从根开始的路径）
preSumCount.put(0L, 1);
return dfs(root, 0L, targetSum, preSumCount);
}
private int dfs(TreeNode node, long currentSum, int target,
Map<Long, Integer> preSumCount) {
// 递归终止：走到空节点
if (node == null) return 0;
// 1. 更新当前路径的前缀和
currentSum += node.val;
int pathCount = 0;
// 2. 【核心】找之前有几个位置的前缀和 = currentSum - target
// 每找到一个，就是以该位置的子节点为起点、当前节点为终点的合法路径
pathCount += preSumCount.getOrDefault(currentSum - target, 0);
// 3. 当前前缀和存入 map（做选择）
preSumCount.put(currentSum, preSumCount.getOrDefault(currentSum, 0) + 1);
// 4. 递归探索左右子树
pathCount += dfs(node.left, currentSum, target, preSumCount);
pathCount += dfs(node.right, currentSum, target, preSumCount);
// 5. 【关键·回溯】离开当前节点，撤销影响（擦橡皮）
// 如果不撤销，右子树的查找会错误地用到左子树分支的前缀和
preSumCount.put(currentSum, preSumCount.get(currentSum) - 1);
return pathCount;
}手算验证：root=[1,2,3], target=3
DFS 路径：1 → 2（前缀和=3），查 3-3=0 → map 有 0 出现 1 次 → count+1。存入 3。
回溯到 1（擦掉前缀和 3）。1 → 3（前缀和=4），查 4-3=1 → map 有 1 出现 1 次 → count+1。存入 4。回溯（擦 4）。回溯（擦 1）。
最终 count = 2（路径 1→2 和 3）。
⏱ 复杂度分析
- 时间复杂度：O(n) —— 每个节点访问一次，HashMap 操作 O(1)
- 空间复杂度：O(n) —— 递归栈最坏 O(n)（树退化为链表）+ HashMap 存最多 n 个前缀和
💡 记忆口诀
“树上前缀和带’擦橡皮’回溯：本子上查 target 差，查完记录自己，走完擦掉痕迹”