前缀和算法实战：连续数组与矩阵区域和

复杂度分析： 时间复杂度 O(n)，空间复杂度 O(n)。哈希表最坏情况下需要存储 n 个不同的前缀和。

Java 实现

class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> hash = new HashMap<>();
        hash.put(0, -1); // 默认存在一个前缀和为 0 的情况
        
        int sum = 0, ret = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += (nums[i] == 0 ? -1 : 1);
            
            if (hash.containsKey(sum)) {
                ret = Math.max(ret, i - hash.get(sum));
            } else {
                hash.put(sum, i);
            }
        }
        return ret;
    }
}

关键点提示： 建议大家在草稿纸上手动推导一遍索引变化，这对理解边界条件很有帮助。特别是当 sum 首次出现时的处理逻辑。

032 矩阵区域和

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

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

算法思路：二维前缀和

这是二维前缀和的典型应用。关键是在填写结果矩阵的时候，要找到原矩阵对应区域的【左上角】以及【右下角】的坐标。

假设当前计算的是 (i, j) 位置的块和，对应的范围是：

• 行范围：[i-k, i+k]
• 列范围：[j-k, j+k]

由于可能会超出矩阵边界，需要进行裁剪：

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

然后我们将求出来的坐标代入到【二维前缀和矩阵】的计算公式上即可。这里要注意下标的映射关系，通常为了处理边界方便，我们会创建一个 (m+1) x (n+1) 的前缀和数组，这样索引可以直接对应。

C++ 实现

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        
        // 1、预处理一个前缀和矩阵，大小为 (m+1) x (n+1)
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        
        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];
            }
        }
        
        // 2、使用前缀和矩阵计算结果
        vector<vector<int>> ret(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // 计算实际矩形区域的四个顶点坐标（注意 +1 偏移）
                int x1 = max(0, i - k) + 1;
                int y1 = max(0, j - k) + 1;
                int x2 = min(m - 1, i + k) + 1;
                int y2 = min(n - 1, j + k) + 1;
                
                // 利用容斥原理计算区域和
                ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        }
        return ret;
    }
};

复杂度分析： 时间复杂度 O(mn)，空间复杂度 O(mn)。我们需要遍历整个矩阵构建前缀和表，再遍历一次生成结果。

Java 实现

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        
        // 1、预处理前缀和矩阵
        int[][] dp = new int[m + 1][n + 1];
        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];
            }
        }
        
        // 2、使用 dp 表计算结果
        int[][] ret = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x1 = Math.max(0, i - k) + 1;
                int y1 = Math.max(0, j - k) + 1;
                int x2 = Math.min(m - 1, i + k) + 1;
                int y2 = Math.min(n - 1, j + k) + 1;
                
                ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        }
        return ret;
    }
}

关键点提示： 建议画图辅助理解坐标映射关系。特别是 dp 数组多开的一行一列如何避免边界判断，这是二维前缀和的标准套路。