LeetCode 304中等前缀和
二维区域和检索 - 矩阵不可变 图解题解
这道题到底在问什么
给定一个二维矩阵 matrix，处理以下类型的多个查询：计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1)，右下角为 (row2, col2)。实现 NumMatrix 类：NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化；int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1)、右下角 (row2, col2) 所描述的子矩阵的元素总和。
- 输入
- ["NumMatrix","sumRegion","sumRegion","sumRegion"]
- 参数
- [[matrix],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
- 输出
- [null,8,11,12]
最优解：一步一步想明白
- 3和 303 一样，题目强调多个查询，就是在提醒你把重复计算提前到初始化阶段。
- 4多开一行一列 0 哨兵后，row1=0 或 col1=0 的查询也能套同一个公式。
- 5self.pre = [[0]*(n+1) for _ in range(m+1)]哨兵 0 让公式不用处理边界特判。此时还没有填入任何 matrix 值；表格坐标是 pre 的坐标，比 matrix 坐标都大 1。
- 6pre[i+1][j+1] = matrix[i][j] + pre[i][j+1] + pre[i+1][j] - pre[i][j]pre[1][1] 表示只覆盖 matrix[0][0] 的小矩形，所以结果是 3。
- 7pre[1][2] = matrix[0][1] + pre[0][2] + pre[1][1] - pre[0][1]第一行第二个数是 0，所以前缀和仍然是 3。
- 8pre[1][3] = matrix[0][2] + pre[0][3] + pre[1][2] - pre[0][2]现在 pre[1][3] 覆盖 matrix[0][0..2]，也就是 3+0+1=4。
- 9pre[2][1] = matrix[1][0] + pre[1][1] + pre[2][0] - pre[1][0]pre[2][1] 覆盖 matrix 前两行第一列：3+5=8。
- 10pre[2][2] = matrix[1][1] + pre[1][2] + pre[2][1] - pre[1][1]上方矩形和左方矩形都包含左上角那块 3，所以要减掉一次 pre[1][1]，这就是二维前缀和最关键的一步。
- 11pre[2][3] = matrix[1][2] + pre[1][3] + pre[2][2] - pre[1][2]继续往右填，依然是“当前值 + 上 + 左 - 左上”。只要每一格都维护这个不变量，整张表就会正确。
- 12pre[3][3] = matrix[2][2] + pre[2][3] + pre[3][2] - pre[2][2]pre[3][3] 覆盖 matrix 左上 3x3 区域。matrix[2][2] 虽然是 0，也要完整套公式。
- 13双重循环继续填完所有 pre[i+1][j+1]后面的格子没有新规则，都是同一个“当前 + 上 + 左 - 左上”公式。初始化结束后，查询只看四个角。
- 14pre[row2+1][col2+1] - pre[row1][col2+1] - pre[row2+1][col1] + pre[row1][col1]四个角分别是：右下 pre[5][4]，上方 pre[2][4]，左方 pre[5][1]，左上重叠 pre[2][1]。pre 坐标比 matrix 坐标多 1。
- 15同一个四角公式右下 pre[3][3] 减上方 pre[1][3]，再减左方 pre[3][1]，最后把左上重叠 pre[1][1] 加回来。
- 16同一个四角公式右下 pre[3][5]、上方 pre[1][5]、左方 pre[3][2]、左上重叠 pre[1][2] 四个角一带入，就得到 12。
- 19只要记住“多算的减掉，少算的补回”，二维公式就不会变成硬背。
⚠️ 容易写错的地方
✗ 错：pre 不多开一行一列
✓ 对：pre 尺寸写成 (m+1) x (n+1)
哨兵能统一处理 row1=0 或 col1=0。
✗ 错：构造时忘记减左上
✓ 对：pre[i][j+1] + pre[i+1][j] 后要减 pre[i][j]
上方和左方的重叠区域被算了两次。
✗ 错：查询时忘记最后加回左上
✓ 对：右下 - 上方 - 左方 + 左上
左上重叠被减了两次，需要补回一次。
✗ 错：混淆 matrix 坐标和 pre 坐标
✓ 对：matrix[i][j] 写到 pre[i+1][j+1]
pre 的第 0 行/列是哨兵。
完整代码（Python）
Python
class NumMatrix:
def __init__(self, matrix):
m, n = len(matrix), len(matrix[0])
self.pre = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
for j in range(n):
self.pre[i + 1][j + 1] = (
matrix[i][j]
+ self.pre[i][j + 1]
+ self.pre[i + 1][j]
- self.pre[i][j]
)
def sumRegion(self, row1, col1, row2, col2):
return (
self.pre[row2 + 1][col2 + 1]
- self.pre[row1][col2 + 1]
- self.pre[row2 + 1][col1]
+ self.pre[row1][col1]
)复杂度
初始化时间
O(mn)
双重循环填完整张 pre 表。
单次查询时间
O(1)
sumRegion 只访问四个 pre 单元格。
空间复杂度
O(mn)
额外保存 (m+1) x (n+1) 的二维前缀和表。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 二维区域和检索 - 矩阵不可变 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「前缀和」，换最直接的暴力解会差在哪？+
前缀和抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。