题目描述
思路解析动画文字版
记住两句:建表是「上加左减左上再加当前」;查矩形和是「大块减上条减左条加左上块」。窗口边界先用 max、min 钳进矩阵,再套查询公式。
总览 · 原始 3×3 矩阵：这是要处理的 3 乘 3 矩阵,行号 i 从上往下 0 到 2,列号 j 从左往右 0 到 2,数值就是 1 到 9 顺着排。k 等于 1,意味着每个中心格要把自己和周围一圈共九个格子加起来,挨着边或角的中心则只能加到落在矩阵里的那几格。先把这张原图记在心里,接下来去搭前缀和表。
建前缀表 · 多一圈零的哨兵：前缀和表 s 比原矩阵多一行一列,这里是 4 乘 4。最上面那一行和最左边那一列全部预填 0,它们是哨兵,代表「一个格子都还没框进来」时的和。有了这圈零,后面递推到第一行第一列时就不用单独写边界判断。中间打点的格子是待会儿要逐个填的真实前缀和。
建前缀表 · 填 s[1][1]：填 s[1][1],它代表原矩阵左上角到第 0 行第 0 列这块的总和。把上面一块 0 和左边一块 0 加起来,这俩在左上角那一小块 0 上重复算了一次,减掉它,再补上当前格自己的 1,得到 1。
建前缀表 · 填 s[1][2]：填 s[1][2],它代表原矩阵左上角到第 0 行第 1 列这块的总和。把上面一块 0 和左边一块 1 加起来,这俩在左上角那一小块 0 上重复算了一次,减掉它,再补上当前格自己的 2,得到 3。
建前缀表 · 填 s[1][3]：填 s[1][3],它代表原矩阵左上角到第 0 行第 2 列这块的总和。把上面一块 0 和左边一块 3 加起来,这俩在左上角那一小块 0 上重复算了一次,减掉它,再补上当前格自己的 3,得到 6。
建前缀表 · 填 s[2][1]：填 s[2][1],它代表原矩阵左上角到第 1 行第 0 列这块的总和。把上面一块 1 和左边一块 0 加起来,这俩在左上角那一小块 0 上重复算了一次,减掉它,再补上当前格自己的 4,得到 5。
建前缀表 · 填 s[2][2]：填 s[2][2],它代表原矩阵左上角到第 1 行第 1 列这块的总和。把上面一块 3 和左边一块 5 加起来,这俩在左上角那一小块 1 上重复算了一次,减掉它,再补上当前格自己的 5,得到 12。
建前缀表 · 填 s[2][3]：填 s[2][3],它代表原矩阵左上角到第 1 行第 2 列这块的总和。把上面一块 6 和左边一块 12 加起来,这俩在左上角那一小块 3 上重复算了一次,减掉它,再补上当前格自己的 6,得到 21。
建前缀表 · 填 s[3][1]：填 s[3][1],它代表原矩阵左上角到第 2 行第 0 列这块的总和。把上面一块 5 和左边一块 0 加起来,这俩在左上角那一小块 0 上重复算了一次,减掉它,再补上当前格自己的 7,得到 12。
建前缀表 · 填 s[3][2]：填 s[3][2],它代表原矩阵左上角到第 2 行第 1 列这块的总和。把上面一块 12 和左边一块 12 加起来,这俩在左上角那一小块 5 上重复算了一次,减掉它,再补上当前格自己的 8,得到 27。
建前缀表 · 填 s[3][3]：填 s[3][3],它代表原矩阵左上角到第 2 行第 2 列这块的总和。把上面一块 21 和左边一块 27 加起来,这俩在左上角那一小块 12 上重复算了一次,减掉它,再补上当前格自己的 9,得到 45。
建前缀表完成 · 任意矩形一查即得：九个真实前缀和全部填好。最右下角 s[3][3] 等于 45,刚好是整个矩阵九个数的总和,可以拿来自检。现在这张表的威力在于:原矩阵里任意一个矩形区域的和,都能用它四个角的值一加减算出来,不用再去逐格累加。下面就用它来回答每个 answer[i][j]。
算 answer[0][0] · 第一步钳窗口：现在算中心在 (0,0) 的窗口。理论窗口是行 -1 到 1、列 -1 到 1。窗口探出了矩阵,被钳成矩形 行 0..1、列 0..1。点亮的这几格 1 + 2 + 4 + 5 就是要相加的区域,直接加是 12,接下来用前缀表一步算出同样的结果。
算 answer[0][0] · 第二步套公式：钳好的矩形是行 0 到 1、列 0 到 1。套区域查询公式:大块到右下角 s[2][2] 是 12,减掉上面那条 s[0][2] = 0,再减掉左边那条 s[2][0] = 0,左上角那块被多减了一次要补回来 s[0][0] = 0。12 减 0 减 0 加 0 等于 12,和刚才直接相加完全一致。
算 answer[0][1] · 第一步钳窗口：现在算中心在 (0,1) 的窗口。理论窗口是行 -1 到 1、列 0 到 2。窗口探出了矩阵,被钳成矩形 行 0..1、列 0..2。点亮的这几格 1 + 2 + 3 + 4 + 5 + 6 就是要相加的区域,直接加是 21,接下来用前缀表一步算出同样的结果。
算 answer[0][1] · 第二步套公式：钳好的矩形是行 0 到 1、列 0 到 2。套区域查询公式:大块到右下角 s[2][3] 是 21,减掉上面那条 s[0][3] = 0,再减掉左边那条 s[2][0] = 0,左上角那块被多减了一次要补回来 s[0][0] = 0。21 减 0 减 0 加 0 等于 21,和刚才直接相加完全一致。
算 answer[1][1] · 第一步钳窗口：现在算中心在 (1,1) 的窗口。理论窗口是行 0 到 2、列 0 到 2。窗口正好落在矩阵内,不需要钳,行 0..2、列 0..2。点亮的这几格 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 就是要相加的区域,直接加是 45,接下来用前缀表一步算出同样的结果。
算 answer[1][1] · 第二步套公式：钳好的矩形是行 0 到 2、列 0 到 2。套区域查询公式:大块到右下角 s[3][3] 是 45,减掉上面那条 s[0][3] = 0,再减掉左边那条 s[3][0] = 0,左上角那块被多减了一次要补回来 s[0][0] = 0。45 减 0 减 0 加 0 等于 45,和刚才直接相加完全一致。
算 answer[1][2] · 第一步钳窗口：现在算中心在 (1,2) 的窗口。理论窗口是行 0 到 2、列 1 到 3。窗口探出了矩阵,被钳成矩形 行 0..2、列 1..2。点亮的这几格 2 + 3 + 5 + 6 + 8 + 9 就是要相加的区域,直接加是 33,接下来用前缀表一步算出同样的结果。
算 answer[1][2] · 第二步套公式：钳好的矩形是行 0 到 2、列 1 到 2。套区域查询公式:大块到右下角 s[3][3] 是 45,减掉上面那条 s[0][3] = 0,再减掉左边那条 s[3][1] = 12,左上角那块被多减了一次要补回来 s[0][1] = 0。45 减 0 减 12 加 0 等于 33,和刚才直接相加完全一致。
算 answer[2][2] · 第一步钳窗口：现在算中心在 (2,2) 的窗口。理论窗口是行 1 到 3、列 1 到 3。窗口探出了矩阵,被钳成矩形 行 1..2、列 1..2。点亮的这几格 5 + 6 + 8 + 9 就是要相加的区域,直接加是 28,接下来用前缀表一步算出同样的结果。
算 answer[2][2] · 第二步套公式：钳好的矩形是行 1 到 2、列 1 到 2。套区域查询公式:大块到右下角 s[3][3] 是 45,减掉上面那条 s[1][3] = 6,再减掉左边那条 s[3][1] = 12,左上角那块被多减了一次要补回来 s[1][1] = 1。45 减 6 减 12 加 1 等于 28,和刚才直接相加完全一致。
回放 · 最终 answer 矩阵：把九个 answer 都按同样两步算出来,就是这张结果矩阵。正中 answer[1][1] 的窗口覆盖整张矩阵,值是 45;四个角因为窗口被剪成 2 乘 2,值最小;四条边上是 2 乘 3。每一格都只花常数步,这就是二维前缀和的好处。
边界都能手验:k 够大时窗口盖满全矩阵每格都是总和;k=0 时原样返回;全 1 矩阵下 answer 就是各窗口的格子个数。
面试三连:建表是容斥「上加左减左上加当前」;查询也是容斥四角加减;前缀和把区域求和从 O(k²) 降到 O(1)、总复杂度 O(m·n) 与 k 无关。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]: m, n = len(mat), len(mat[0]) s = [[0] * (n + 1) for _ in range(m + 1)] for i, row in enumerate(mat, 1): for j, x in enumerate(row, 1): s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x ans = [[0] * n for _ in range(m)] for i in range(m): for j in range(n): x1, y1 = max(i - k, 0), max(j - k, 0) x2, y2 = min(m - 1, i + k), min(n - 1, j + k) ans[i][j] = ( s[x2 + 1][y2 + 1] - s[x1][y2 + 1] - s[x2 + 1][y1] + s[x1][y1] ) return ans复杂度
- 时间：O(m·n)，建前缀表扫一遍全矩阵是 O(m·n);算答案再扫一遍全矩阵,每个 answer[i][j] 靠前缀表只做四次加减、常数时间。两段都是线性,合起来 O(m·n)。比逐格累加窗口的 O(m·n·k²) 快得多
- 空间：O(m·n)，按峰值算:前缀和表 s 是 (m+1)×(n+1),和原矩阵同量级,平方级。输出矩阵 answer 也是 m×n 但通常算进结果不计;没有递归,不额外吃栈
易错点
面试追问把动画讲成自己的话
追问二维前缀和的建表递推为什么是「上加左减左上再加当前」?
追问查询任意矩形和的公式怎么来的?
追问不用前缀和,直接对每个窗口累加行不行?复杂度差多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
连通网络的操作次数
LeetCode 1319 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题