力扣1314——矩阵区域和（二维前缀和）

力扣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.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;
    }
};