class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
}
};
1314. 矩阵区域和
给你一个 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.lengthn == mat[i].length1 <= m, n, k <= 1001 <= mat[i][j] <= 100原站题解
python3 解法, 执行用时: 124 ms, 内存消耗: 16.4 MB, 提交时间: 2022-11-21 15:50:03
'''
二维前缀和
'''
class Solution:
def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
m, n = len(mat), len(mat[0])
P = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]
def get(x, y): # 获取指定坐标前缀和
x = max(min(x, m), 0)
y = max(min(y, n), 0)
return P[x][y]
ans = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
ans[i][j] = get(i + K + 1, j + K + 1) - get(i - K, j + K + 1) - get(i + K + 1, j - K) + get(i - K, j - K);
return ans