图解算法通识讲义经典套路
前缀和与差分数组空间换时间
核心心智模型：前人栽树，后人乘凉；预处理累加前缀，任意连续区间的和与积瞬间 O(1) 产出。
核心交互式算法图解演练沙盒
前缀和模型
前缀和数组与 O(1) 区间求和演算
步骤 1 / 3
当前查询区间：[1, 3]sumRange(1, 3) = P[4] - P[1] = 17 - 1 = 16
单次查询: O(1) 常数时间原数组 nums (长度 N):
1
nums[0]
7
nums[1]
3
nums[2]
6
nums[3]
5
nums[4]
6
nums[5]
前缀和数组 prefix (长度 N+1):
0
P[0]
1
P[1] (减数)
8
P[2]
11
P[3]
17
P[4] (被减数)
22
P[5]
28
P[6]
区间 [1...3] 求和：检索 7 + 3 + 6。直接通过前缀和做差 P[4] - P[1] 瞬间算出 16，耗时 O(1)。
关键操作与时空复杂度速查对照表
| 操作 / 算法阶段 | 平均时间 | 最坏时间 | 空间复杂度 | 核心底层机制 |
|---|---|---|---|---|
| 前缀和预处理 | O(N) | O(N) | O(N) | 单次线性扫描累加构建。 |
| 区间子数组和查询 | O(1) | O(1) | O(1) | 两次读取前缀数组做差。 |
template.java
int[] prefix = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
int rangeSum = prefix[r + 1] - prefix[l];解题核心心法提炼
- 前缀和数组长度通常设置为 n + 1，并将 prefix[0] 设为 0，防止处理左边界 0 时出现负下标。
- 除自身以外数组的乘积是前缀积与后缀积的经典结合。
- 差分数组是前缀和的逆运算，用于在 O(1) 时间内完成对区间所有元素的频繁增减操作。
常见踩坑警示与避坑指南
- 下标偏移对应关系混乱：忘记 prefix[i] 对应的是原始数组的前 i 个元素（0 到 i-1）。
对应 Hot 100 实战题目突围
原理已掌握！立即进入沉浸式工作台开始实战演练，强化代码肌肉记忆