前缀和是面试中最被低估的优化技巧。预计算 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[right1] - prefix[left]查询示例sumRange(1, 3)nums[1] nums[2] nums[3] 2 3 4 9 通过前缀和prefix[31] - 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. 区域和检索 - 数组不可变Easy3.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 全部元素之和 -33.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: vectorint prefix; public: NumArray(vectorint 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的子数组Medium4.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]索引24.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)核心洞察子数组[i1..j]的和 prefix[j] - prefix[i]。要统计prefix[j] - prefix[i] k的个数等价于遍历到j时统计之前出现过多少个prefix[j] - k。公式推导子数组 [i1..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) { MapInteger, 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(vectorint nums, int k) { unordered_mapint, 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]统一加valdiff[l] val, diff[r1] - val恢复数组nums[i] nums[i-1] diff[i]特性前缀和差分数组解决的问题多次区间查询多次区间修改核心操作预计算 → O(1) 查询区间修改 O(1) → 恢复典型应用303, 560, 3041109, 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, 数据结构