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

算法总结及流程解析：

32. 矩阵区域和

题目链接：

1314. 矩阵区域和 - 力扣（LeetCode）

题目描述：

题目示例：

解法：

算法思路：

二维前缀和的简单应用题，关键就是我们在填写结果矩阵的时候，要找到原矩阵对于区域的左上角以及右下角的坐标（建议画个图辅助理解，坐标关系会更清晰）。

• 左上角坐标：x1 = i - k，y1 = j - k，但是由于可能会超过矩阵的范围，因此需要对 0 取一个 max。修正后的坐标为：x1 = max(0, i - k)，y1 = max(0, j - k)；
• 右下角坐标：x2 = i + k，y2 = j + k，但是由于可能会超过矩阵的范围，因此需要对 m-1，以及 n - 1 取一个 min。修正后的坐标为：x2 = min(m-1, i+k)，y2 = min(n-1, j+k)。

然后将求出来的坐标代入到二维前缀和矩阵的计算公式上即可（注意下标的映射关系）。

C++ 算法代码：

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>> sums(m + 1, vector<int>(n + 1, 0));
        vector<vector<int>> ret(m, vector<int>(n, 0));
        
        // 构建二维前缀和数组
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                sums[i + 1][j + 1] = mat[i][j] + sums[i][j + 1] + sums[i + 1][j] - sums[i][j];
            }
        }
        
        // 计算每个位置的块和
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                // max 和 min 是为了处理越界情况
                // i + 1 和 j + 1 的目的就是为了和 mat 进行映射关系，sums[i + 1][j + 1] -> mat[i][j]
                // 然后 i - k 实际上是 i + 1 - k - 1，i + 1 依然是与 mat 进行映射关系
                ret[i][j] = sums[min(m, i + 1 + k)][min(n, j + 1 + k)] 
                          - sums[max(0, i - k)][min(n, j + 1 + k)] 
                          - sums[min(m, i + 1 + k)][max(0, j - k)] 
                          + sums[max(0, i - k)][max(0, j - k)];
            }
        }
        return ret;
    }
};

算法总结及流程解析：

以上就是两道题目的完整解析。连续数组将 0/1 转换后用前缀和 + 哈希表寻找和为 0 的最长子数组；矩阵区域和通过二维前缀和快速计算矩阵区域和，注意处理边界条件。希望这些内容能对你有所启发。