到O(1)的降维打击)
前缀和是面试中"最被低估"的优化技巧。预计算 O(n) + 查询 O(1) 的经典模式，掌握后能解决几乎所有"区间和"类问题。
一、引言
🤔思考：面试官给你一个数组，要你快速回答"索引 2 到 7 的和是多少"。你写了一个循环累加，O(n) 搞定。面试官说："我有 100 万次这样的查询，怎么办？" 你的 O(n) × 100 万 = 1000 亿次操作，显然不行。
这就是前缀和（Prefix Sum）要解决的问题。
前缀和是一种预计算优化技巧：先花 O(n) 时间预处理一个前缀和数组，然后每次区间和查询只需要 O(1) 时间。这是典型的空间换时间——用 O(n) 的额外空间，把查询从 O(n) 降到 O(1)。
本文围绕两个经典题目展开：
303. 区域和检索 - 数组不可变（Easy）—— 前缀和的入门模板，展示静态前缀和的核心用法
560. 和为K的子数组（Medium）—— 前缀和 + 哈希表优化，从静态预计算到动态统计的进阶
本期是「数据结构与算法面试精讲」系列第16篇。
二、前缀和基础
2.1 什么是前缀和？
前缀和（Prefix Sum）是指数组从开头到某个位置的所有元素之和。
对于数组nums，定义前缀和数组prefix，其中prefix[i]表示nums[0]到nums[i-1]的和（即不包含nums[i]本身）：
prefix[i] = sum(nums[0..i-1])这种定义方式（左闭右开）的好处是：prefix[0] = 0，边界处理更统一。
2.2 前缀和的计算与使用
计算前缀和数组：
prefix[0] = 0 for i in 1..n: prefix[i] = prefix[i-1] + nums[i-1]使用前缀和查询区间和：
sumRange(left, right) = prefix[right+1] - prefix[left]查询示例：sumRange(1, 3)=nums[1] + nums[2] + nums[3]= 2 + 3 + 4 = 9 通过前缀和：prefix[3+1] - prefix[1]=prefix[4] - prefix[1]= 10 - 1 = 9 ✅
2.3 暴力 vs 前缀和对比
算法 | 预处理时间 | 单次查询时间 | 空间 |
|---|---|---|---|
暴力枚举 | O(1) | O(n) | O(1) |
前缀和 | O(n) | O(1) | O(n) |
关键洞察：当查询次数远多于数组长度时，前缀和的效果最显著。一次预计算 O(n) 的成本，被后续大量 O(1) 查询摊薄。
三、303. 区域和检索 - 数组不可变（Easy）
3.1 题目描述
给定一个整数数组nums，处理多个查询sumRange(i, j)，返回数组从索引i到j的元素和。
示例：
输入: nums = [-2, 0, 3, -5, 2, -1] sumRange(0, 2) → 1 （-2 + 0 + 3 = 1） sumRange(2, 5) → -1 （3 + (-5) + 2 + (-1) = -1） sumRange(0, 5) → -3 （全部元素之和 = -3）3.2 前缀和解法
核心思路：在构造函数中预计算前缀和数组，sumRange直接查表。
class NumArray: def __init__(self, nums: List[int]): self.prefix = [0] * (len(nums) + 1) for i in range(len(nums)): self.prefix[i + 1] = self.prefix[i] + nums[i] def sumRange(self, left: int, right: int) -> int: return self.prefix[right + 1] - self.prefix[left]class NumArray { private int[] prefix; public NumArray(int[] nums) { prefix = new int[nums.length + 1]; for (int i = 0; i < nums.length; i++) { prefix[i + 1] = prefix[i] + nums[i]; } } public int sumRange(int left, int right) { return prefix[right + 1] - prefix[left]; } }class NumArray { private: vector<int> prefix; public: NumArray(vector<int>& nums) { prefix.resize(nums.size() + 1, 0); for (int i = 0; i < nums.size(); i++) { prefix[i + 1] = prefix[i] + nums[i]; } } int sumRange(int left, int right) { return prefix[right + 1] - prefix[left]; } };复杂度分析：
时间复杂度：初始化 O(n)，查询 O(1)
空间复杂度：O(n)
3.3 面试追问
追问1：如果数组很大（比如 10^9 个元素），无法全量存内存怎么办？
分段前缀和——把数组分成若干块（block），每块预计算块内和。查询时完整的块直接用块内和，不完整的块逐个累加。块大小设为sqrt(n)，查询复杂度 O(√n)，空间 O(√n)。
追问2：如果数组在查询之间会改变呢？
那就不能用静态前缀和。需要树状数组（Fenwick Tree）或线段树（Segment Tree），支持动态更新和区间查询。
四、560. 和为K的子数组（Medium）
4.1 题目描述
给定一个整数数组nums和一个整数k，统计该数组中和为k的连续子数组的个数。
示例 1：
输入: nums = [1, 1, 1], k = 2 输出: 2 解释: [1, 1]（索引0-1）和 [1, 1]（索引1-2）两个子数组示例 2：
输入: nums = [1, 2, 3], k = 3 输出: 2 解释: [1, 2]（索引0-1）和 [3]（索引2）4.2 暴力解法（O(n²)）
class Solution: def subarraySum(self, nums: List[int], k: int) -> int: count = 0 for i in range(len(nums)): s = 0 for j in range(i, len(nums)): s += nums[j] if s == k: count += 1 return count当nums.length达到 2×10⁴ 时，O(n²) 的 4 亿次操作必然超时。
4.3 前缀和 + 哈希表优化（O(n)）
核心洞察：子数组[i+1..j]的和 =prefix[j] - prefix[i]。要统计prefix[j] - prefix[i] = k的个数，等价于遍历到j时，统计之前出现过多少个prefix[j] - k。
公式推导：
子数组 [i+1..j] 的和 = k → prefix[j] - prefix[i] = k → prefix[i] = prefix[j] - k三语言实现：
class Solution: def subarraySum(self, nums: List[int], k: int) -> int: prefix_map = {0: 1} prefix_sum = 0 count = 0 for num in nums: prefix_sum += num count += prefix_map.get(prefix_sum - k, 0) prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1 return countclass Solution { public int subarraySum(int[] nums, int k) { Map<Integer, Integer> prefixMap = new HashMap<>(); prefixMap.put(0, 1); int prefixSum = 0, count = 0; for (int num : nums) { prefixSum += num; count += prefixMap.getOrDefault(prefixSum - k, 0); prefixMap.put(prefixSum, prefixMap.getOrDefault(prefixSum, 0) + 1); } return count; } }class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map<int, int> prefixMap; prefixMap[0] = 1; int prefixSum = 0, count = 0; for (int num : nums) { prefixSum += num; count += prefixMap[prefixSum - k]; prefixMap[prefixSum]++; } return count; } };复杂度分析：时间复杂度 O(n)，空间复杂度 O(n)。
4.4 面试追问
追问1：如果数组包含负数怎么办？解法不变。560 题本身就支持负数。追问2：如果要求返回子数组的起始和结束位置？哈希表改存prefix_sum → [index_list]。
五、差分数组简介
差分数组（Difference Array）与前缀和是"对偶"关系。前缀和解决"多次区间查询"，差分数组解决"多次区间修改"。
定义：diff[i] = nums[i] - nums[i-1]（其中diff[0] = nums[0]）
核心操作：
区间
[l, r]统一加val：diff[l] += val, diff[r+1] -= val恢复数组：
nums[i] = nums[i-1] + diff[i]
特性 | 前缀和 | 差分数组 |
|---|---|---|
解决的问题 | 多次区间查询 | 多次区间修改 |
核心操作 | 预计算 → O(1) 查询 | 区间修改 O(1) → 恢复 |
典型应用 | 303, 560, 304 | 1109, 1094 |
六、家族题梯度
题号 | 题目 | 难度 | 核心技巧 |
|---|---|---|---|
303 | 区域和检索 | ⭐ Easy | 静态前缀和模板 |
304 | 二维区域和检索 | ⭐⭐ Medium | 二维前缀和 |
560 | 和为K的子数组 | ⭐⭐ Medium | 前缀和 + 哈希表 |
523 | 连续子数组和 | ⭐⭐ Medium | 前缀和 + 哈希表（模） |
974 | 和可被K整除的子数组 | ⭐⭐ Medium | 前缀和 + 模运算 |
1109 | 航班预订统计 | ⭐⭐ Medium | 差分数组模板 |
1094 | 拼车 | ⭐⭐ Medium | 差分数组应用 |
学习建议：先做 303 和 304 掌握静态前缀和模板 → 再做 560 和 523 理解前缀和 + 哈希表 → 最后做 1109 和 1094 掌握差分数组。
参考资料
LeetCode 303. 区域和检索 - 数组不可变
LeetCode 560. 和为K的子数组
LeetCode 1109. 航班预订统计（差分数组典型题）
标签：前缀和, 差分数组, 算法面试, LeetCode, 数据结构
