前缀和与差分数组——从O(n²)到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)。

本文围绕两个经典题目展开：

1. 303. 区域和检索 - 数组不可变（Easy）—— 前缀和的入门模板，展示静态前缀和的核心用法

2. 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(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 count

class 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]

六、家族题梯度

学习建议：先做 303 和 304 掌握静态前缀和模板 → 再做 560 和 523 理解前缀和 + 哈希表 → 最后做 1109 和 1094 掌握差分数组。

参考资料

• LeetCode 303. 区域和检索 - 数组不可变

• LeetCode 560. 和为K的子数组

• LeetCode 1109. 航班预订统计（差分数组典型题）

标签：前缀和, 差分数组, 算法面试, LeetCode, 数据结构