题目
难度：中等
给定一个二维矩阵 matrix，以下类型的多个请求：
- 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为
(row1, col1) ， 右下角 为 (row2, col2) 。
实现 NumMatrix 类：
NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、 右下角 (row2, col2) 所描述的子矩阵的元素 总和 。
示例 1：
输入:
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出:
[null, 8, 11, 12]
解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 200-10^5 <= matrix[i][j] <= 10^50 <= row1 <= row2 < m0 <= col1 <= col2 < n- 最多调用
10^4 次 sumRegion 方法
初始化各对象
给定的矩阵matrix的大小m*n
维护一个二维数组sum，为了方便我们把sum的大小设置为[m+1][n+1]。将比matrix多出来的一行一列（sum[0][j]和sum[i][0]）全部初始化为0。
存储的方法：存储矩阵matrix下标从[0][0]开始到[i][j]的子矩阵的所有元素之和到数组sum的对应位置，对应关系会在下面进行解析。
如下图：
如何实现呢？
总不能遍历sum直接计算对应子矩阵所有元素然后存入吧，如此麻烦，与我们追求更高效率的本心背道而驰。
维护数组sum[i][j]
如下图，由于我们是从左到右，从上到下为sum数组赋值，所以我们可以利用已经求出来的sum的某些元素来推导出sum[i][j]的值。由原理得sum[i][j]可以看成sum[i-1][j]加上矩阵matrix的第i行计算出来的。而矩阵matrix的第i行元素之和不用遍历求出，可以使用sum[i][j-1]-sum[i-1][j-1]求出来第i行前j个元素的和，再加上matrix[i][j]即求出了该行元素和。注意这里sum的有效部分的下标从1开始，所以应该加上matrix[i-1][j-1]。
因此sum[i][j]可被赋值为
sum[i][j]=sum[i-1][j]+(sum[i][j-1]-sum[i-1][j-1])+matrix[i-1][j-1]
![求sum[i][j]的值](https://s1.imagehub.cc/images/2024/11/20/1c74f7cbe3e4788d4cd8f8ba01be659f.png)
这个结论也解释了为什么sum的有效部分下标从1开始，这样相当于抽象出来了matrix的第-1行和第-1列，假若下标从0开始这个结论就不适用于matrix下标i或j为0的情况了，这时i-1或j-1是-1，是无效的下标，程序会报错。主要就是解决matrix[0][0]到matrix[i][0]和matrix[0][j]这若干区间元素和的计算使它也满足上面推导出的式子，而无需做特判。可以理解为为matrix "添加" 了下标为-1的行和下标为-1的列，sum[i][j]计算的是从matrix[-1][-1]开始到matrix[i][j]的子矩阵的所有元素之和，由于下标为-1的行和下标为-1的列所有的元素都初始化为0了，因此matrix[-1][-1]开始到matrix[i][j]的子矩阵的所有元素之和就和从matrix[0][0]开始到matrix[i][j]的子矩阵所有元素之和相等了。经过这么转换之后sum的下标与matrix并不是一一对应的，matrix下标从[0][0]开始到[i][j]的子矩阵的所有元素之和对应的是sum[i+1][j+1]。
讲的稍微有些啰嗦，但是只要您把原理熟稔于心，实际写起来就远没有这么麻烦。
至此前缀和数组sum已经维护完毕，下面就是求本题的答案了
求出答案
题目要求的是给定两元素为主对角线的子矩阵所有元素之和。笔者仍然结合图片进行说明。笔者是画图苦手，这图画的略微抽象且一定程度上不合逻辑……一定要结合文字描述食用！
如图，将matrix[0][0]到matrix[row2][col2]这一子矩阵划为四部分。红色部分表示的为所求的子矩阵。这样就很明了了：所求子矩阵元素之和等于matrix[0][0]到matrix[row2][col2]这一子矩阵减去肉色的部分和两块黄色的部分。其中右上角黄色的部分可以表示为sum[row1-1+1][col2+1]-sum[row1-1+1][col1-1+1]（注意sum数组与matrix矩阵下标的转换关系，此处已做转换，下同），左下角黄色部分可以表示为sum[row2+1][col1-1+1]-sum[row1-1+1][col1-1+1]，诶↗，盲生你发现了华点，两个式子的减数都是sum[row1-1+1][col1-1+1]，这不就是肉色的部分吗！也就是在计算两块黄色部分的时候，肉色部分已经总共被减了两次。因此表达式可写为如下形式：
res=sum[row2+1][col2+1]-sum[row1][col2+1]-sum[row2+1][col1]+sum[row1][col1];
直接把结果return就好了。
完整AC代码如下：
class NumMatrix {
public:
vector<vector<int>> sum;
NumMatrix(vector<vector<int>>& matrix) {
int m=matrix.size();int n=matrix[0].size();
sum.resize(m+1,vector<int>(n+1,0));
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+matrix[i-1][j-1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return sum[row2+1][col2+1]-sum[row1][col2+1]-sum[row2+1][col1]+sum[row1][col1];
}
};
时间复杂度 O(m×n),为维护前缀和数组sum，访问的时间为O(1)
学以致用！
再看2024年11月18日Leetcode每日一题。我们可以用二位前缀和的方法来解这道题。
661. 图片平滑器
难度：简单
图像平滑器 是大小为 3 × 3 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。
每个单元格的 平均灰度 定义为：该单元格自身及其周围的 8 个单元格的平均值，结果需向下取整。（即，需要计算蓝色平滑器中 9 个单元格的平均值）。
如果一个单元格周围存在单元格缺失的情况，则计算平均灰度时不考虑缺失的单元格（即，需要计算红色平滑器中 4 个单元格的平均值）。
给你一个表示图像灰度的 m × n 整数矩阵 img ，返回对图像的每个单元格平滑处理后的图像 。
示例 1:
输入:img = [[1,1,1],[1,0,1],[1,1,1]]
输出:[[0, 0, 0],[0, 0, 0], [0, 0, 0]]
解释:
对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0
对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0
对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0
示例 2:
输入: img = [[100,200,100],[200,50,200],[100,200,100]]
输出: [[137,141,137],[141,138,141],[137,141,137]]
解释:
对于点 (0,0), (0,2), (2,0), (2,2): floor((100+200+200+50)/4) = floor(137.5) = 137
对于点 (0,1), (1,0), (1,2), (2,1): floor((200+200+50+200+100+100)/6) = floor(141.666667) = 141
对于点 (1,1): floor((50+200+200+200+200+100+100+100+100)/9) = floor(138.888889) = 138
提示:
m == img.lengthn == img[i].length1 <= m, n <= 2000 <= img[i][j] <= 255
解法一：直接遍历
思路：
不黄但很暴力，不多解释。问就是数据量少 [doge]。
完整代码：
class Solution {
public:
vector<vector<int>> imageSmoother(vector<vector<int>>& img) {
int m=img.size(),n=img[0].size();
vector<vector<int>> ans=img;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
int cnt=0,res=0;
for(int dx=i-1;dx<=i+1;dx++){
if(dx<0||dx>=m)
continue;
for(int dy=j-1;dy<=j+1;dy++){
if(dy<0||dy>=n)
continue;
res+=img[dx][dy];cnt++;
}
}
res/=cnt;
ans[i][j]=res;
}
}
return ans;
}
};
时间复杂度为O(m×n×k^2)，k为平滑器的边长，题目中规定平滑器的大小为3×3数据量不算大。但是如果题目给的边长更大，那么暴力就要TLE了。在这个方法中有大量元素被重复用于计算求和，效率实在不高。
解法二：二维前缀和
思路：
维护一个二维数组sum[m+2][n+2]作为前缀和数组，具体维护方式和上面的一样，sum[i][j]表示的还是以[0][0]和[i-1][j-1]为主对角线两端点的子矩阵的所有元素之和。sum[i][j]赋值的方法和刚才的结论还是相同的。
接下来先介绍对sum进行分块处理求出我们想要的平滑器中元素之和。
这里我们要求的是这个 以img[i][j]为中心 的平滑器包含的所有元素的平均值，我们表示子矩阵（平滑器）的下标和前缀和数组下标的对应关系也发生了改变，要求以img[i][j]为中心的平滑器的所有元素之和，结合下图，我们要先求出从img[0][0]到img[i+1][j+1]这个子矩阵的所有元素之和即sum[i+2][j+2]。然后分别减去两块黄色和一块粉色部分，与刚才的方法相同。
平滑器的和的表达式为：
int Sum=sum[i+1+1][j+1+1]-sum[i-1][j+1]-sum[i+1+1][j-1]+sum[i-1][j-1];
在计算矩阵img以下边缘某元素或右边沿某元素为中心的平滑器中元素的和时，由于本题img矩阵和sum的对应关系与上一道题目不同，若创建数组为sum[m+1][n+1]，会导致下标无效（此时下标i>=m+1或j>=n+1），所以这里sum的大小改为了sum[m+2][n+2]。
之后定义四个变量a,b,c,d分别代表平滑器的上，下，左，右四边界，并以此求出平滑器中有效的元素有多少个，方便求平均值。如果a,b,c,d标记的超出矩阵img范围则置为0或m-1或n-1，可以用取最小值的操作来实现。这么操作优化掉了遍历计数,且便于访问sum中的值用于求和。则平滑器的和的表达式可写作：
int Sum=sum[c+1][d+1]-sum[a][d+1]-sum[c+1][b]+sum[a][b];
平滑器中包含元素的个数可写作：
int cnt=(c-a+1)*(d-b+1);
将Sum/cnt的结果加入答案数组即可。int类型相除若有余数则向下取整。
####完整代码：
时间复杂度为O(m×n)，与暴力比有一定的优化，但是由于本题数据量，优化不是很显著（有一次还是做到0ms了的，LC评测机有的慢有的快）。
