前缀和算法：从一道 LeetCode 题看区间求和优化思想

1. 引言：区间求和的性能困境

给定一个数组，多次查询某个区间[i, j]的元素之和。

最直观的做法是：

for(intk=i;k<=j;k++){sum+=nums[k];}

时间复杂度：

❌ 每次查询 O(n)

当查询次数很多时，性能会急剧下降。

这类问题的本质是：

👉重复计算大量相同区间数据

而前缀和，正是解决这一问题的利器。

2. 什么是前缀和？

前缀和（Prefix Sum）指的是：

一个数组中，从第 0 个元素到当前位置的累加和。

定义：

prefix[i] = nums[0] + nums[1] + ... + nums[i-1]

也就是说：

• prefix[0] = 0
• prefix[1] = nums[0]
• prefix[2] = nums[0] + nums[1]

这种设计可以极大方便区间计算。

3. 示例代码解析

题目代码如下：

classNumArray{int[]sums;publicNumArray(int[]nums){intn=nums.length;sums=newint[n+1];for(inti=0;i<n;i++){sums[i+1]=sums[i]+nums[i];}}publicintsumRange(inti,intj){returnsums[j+1]-sums[i];}}

可参考灵神题解：前缀和，附扩展问题（Python/Java/C++/C/Go/JS/Rust）

这是 LeetCode 303：区域和检索 的经典解法。

4. 前缀和数组的构建过程

4.1 为什么长度是 n+1？

sums=newint[n+1];

多开一个位置，是为了统一计算公式。

令：

sums[0] = 0

这样可以避免边界特判。

否则得判断边界：

sumRange(i,j)=sums[j]-sums[i-1]// 当 i > 0 时sumRange(0,j)=sums[j]// 当 i = 0 时

4.2 构造过程分析

核心代码：

sums[i+1]=sums[i]+nums[i];

假设：

nums = [2, 4, 6, 8]

构造过程：

最终：

sums = [0, 2, 6, 12, 20]

5. 区间求和公式推导

查询代码：

returnsums[j+1]-sums[i];

为什么这样就能得到[i, j]的和？

5.1 数学推导

根据定义：

sums[j+1] = nums[0] + ... + nums[j] sums[i] = nums[0] + ... + nums[i-1]

相减：

sums[j+1] - sums[i] = nums[i] + ... + nums[j]

刚好是目标区间。

5.2 图形理解

0 ---- i ---- j ---- n |------|====|--------| 去掉 保留

前面减掉，只留下中间。

6. 时间复杂度分析

对比暴力法：

👉以空间换时间的经典案例

7. 为什么前缀和如此重要？

前缀和是很多高级算法的基础，包括：

• 滑动窗口
• 差分数组
• 二维矩阵处理
• 哈希优化
• 动态规划

几乎是刷题必备技能。

8. 常见扩展题型

8.1 区间和为 K 的子数组

560. 和为 K 的子数组

思想：

前缀和 + HashMap

sum[i] - sum[j] = k

8.2 二维前缀和

用于矩阵求和：

sum[i][j] = 左 + 上 - 左上 + 当前

常见于图像处理、地图统计。

8.3 差分数组（前缀和的逆运算）

区间修改问题：

diff[l]++ diff[r+1]--

最后再前缀和还原。

9. 什么时候不适合用前缀和？

前缀和适用于：

✔ 静态数组
✔ 多次查询
✔ 无修改操作

不适合：

❌ 高频修改数组
❌ 动态插入删除

此时应该考虑：

• 线段树
• 树状数组

10. 面试高频问题

Q1：为什么 sums 多开一位？

统一公式，减少边界判断。

Q2：能不能不用额外空间？

理论上可以边算边存，但查询效率会下降。

Q3：前缀和和滑动窗口的区别？