算法实战：前缀和技巧解析（连续数组与矩阵区域和）

32. 矩阵区域和

题目链接： 1314. 矩阵区域和 - LeetCode

题目描述： 给你一个 m x n 的矩阵 mat 和一个整数 k，请你返回一个矩阵 answer，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：

• i - k <= r <= i + k
• j - k <= c <= j + k
• (r, c) 在矩阵内。

解法思路

这是二维前缀和的典型应用。关键在于如何快速计算任意矩形区域的和。我们通常使用二维前缀和数组 dp，其中 dp[i][j] 表示以 (0,0) 为左上角、(i-1,j-1) 为右下角的矩形区域和。

对于目标点 (i, j) 及其周围半径为 k 的区域，我们需要确定其左上角和右下角坐标。由于边界限制，坐标需要进行修正：

• 左上角：x1 = max(0, i - k), y1 = max(0, j - k)
• 右下角：x2 = min(m - 1, i + k), y2 = min(n - 1, j + k)

利用容斥原理，区域和可以通过四个角的值计算得出。注意 dp 数组通常多开一行一列以简化边界判断。

C++ 代码实现

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        // dp 数组多开一行一列，方便处理边界
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        vector<vector<int>> answer(m, vector<int>(n));

        // 预处理出来一个 dp 数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; 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 < m; i++) {
            for (int j = 0; j < n; j++) {
                // 注意下标映射关系，dp 比原矩阵多 1
                int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
                int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1;
                
                answer[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        }
        return answer;
    }
};