1314. 矩阵区域和难度中等
给你一个 m * n 的矩阵 mat 和一个整数 K ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：
*
i - K <= r <= i + K, j - K <= c <= j + K
*
(r, c) 在矩阵内。
示例 1：
输入：mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
输出：[[12,21,16],[27,45,33],[24,39,28]]
示例 2：
输入：mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
输出：[[45,45,45],[45,45,45],[45,45,45]]
提示：
*
m == mat.length
*
n == mat[i].length
*
1 <= m, n, K <= 100
*
1 <= mat[i][j] <= 100v
个人思路：计算出r和c的范围，将他们的不同组合叠加，放到对应answer位置
代码1.0
class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {
int row=mat.size();int column=mat[0].size();vector<vector<int>> answer(row,vector<int>(column,0));for(int i=0;i<row;++i){
for(int j=0;j<column;++j){
int be1=(i-K)<0?0:(i-K);int en1=(i+K)>row?row:(i+K);int be2=(j-K)<0?0:(j-K);int en2=(j+K)>column?column:(j+K);int tol=0;for(;be1<=en1;++be1){
for(;be2<=en2;++be2){
tol+=mat[be1][be2];}}answer[i][j]=tol;}}return answer;}
};
结果：复杂度太高，溢出错误
题解收获：
新的知识点：“二维前缀和”
原矩阵 arr[r][c]
用于存储二维前缀和的矩阵P[r+1][c+1]
P[i][j]即为arr中以[0][0]为左上角，[i-1][j-1]为右下角的矩阵值的总和
P矩阵的第一行和第一列为0
代码2.0：class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {
int row = mat.size();int column = mat[0].size();vector<vector<int>> dp(row + 1, vector<int>(column + 1,0));vector<vector<int>> answer(row, vector<int>(column));//完善数组mat的二维前缀和数组dpfor (int i = 1; i <= row; ++i){
for (int j = 1; j <= column; ++j){
dp[i][j] =dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i-1][j-1];}}//用二维前缀和数组dp来求得结果for (int i = 0; i < row; ++i){
for (int j = 0; j < column; ++j){
int leftx = max(0, i - K);int lefty = max(0, j - K);int rightx = min(row-1, i + K);int righty = min(column-1, j + K);answer[i][j]=dp[rightx+1][righty+1]-dp[leftx][righty+1]-dp[rightx+1][lefty]+dp[leftx][lefty];}}return answer;}
};
思路：
1：为mat数组准备好他的二维前缀和数组dp
关键公式：dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mat[i-1][j-1]
2：用二位前缀和数组dp求得answer
answer[i][j]意思即为求 以左上角为mat[i-k][j-k],右下角为mat[i+k][j+k]
的矩阵和
关键公式：answer[i][j]=dp[i+k+1][j+k+1]+dp[i-k][j-k]
-dp[i-k][j+1+k]-dp[i+k+1][j-k]