给你一个 m x 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] <= 100
每个位置[i][j]的答案对应[i-k][j-k] 到[i+k][j+k] 这个方形区域内所有数的和；
看数据量不大，应该可以每次暴力做，时间复杂度
O
(
m
∗
n
∗
k
2
)
O(m*n*k^2)
O(m∗n∗k2)
更高效的做法是二维前缀和，复杂度
O
(
m
∗
n
)
O(m*n)
O(m∗n)；
首先算出每个位置之前的前缀和；
然后算出每个位置对应的方块区域的左上角和右下角，注意边界判断
每个区域的和就是右下角+左上角-左下角-右上角。
因为前缀和数组多开一位，0行0列保持为0，所以右下角要多加一
class Solution {
public:
vector> matrixBlockSum(vector>& mat, int k) {
int m = mat.size();
int n = mat[0].size();
vector> sums(m+1, vector(n+1, 0));
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
sums[i][j] += sums[i][j-1] + mat[i-1][j-1];
}
}
for(int j = 1; j <= n; j++) {
for(int i = 1; i <= m; i++) {
sums[i][j] += sums[i-1][j];
}
}
vector> ans(m, vector(n, 0));
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
int x1 = i - k >= 0 ? i - k : 0;
int y1 = j - k >= 0 ? j - k : 0;
int x2 = i + k + 1 <= m ? i + k + 1 : m;
int y2 = j + k + 1 <= n ? j + k + 1 : n;
ans[i][j] = sums[x2][y2] + sums[x1][y1] - sums[x2][y1] - sums[x1][y2];
}
}
return ans;
}
};
