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

class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> hash = new HashMap<>();
        // 默认存在一个前缀和为 0 的情况
        hash.put(0, -1);
        
        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;
    }
}

时间复杂度：O(n)，空间复杂度：O(n)。

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) 在矩阵内。

算法思路：二维前缀和

这是一道典型的二维前缀和应用题。关键在于确定每个查询区域的左上角和右下角坐标，并利用预处理好的前缀和矩阵进行 O(1) 查询。

对于矩阵中任意一点 (i, j)，其对应的区域范围是 [i-k, i+k] x [j-k, j+k]。由于边界限制，我们需要对坐标进行裁剪：

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

为了简化边界处理，通常构建一个大小为 (m+1) x (n+1) 的前缀和矩阵 dp，其中 dp[i][j] 表示原矩阵中从 (0,0) 到 (i-1, j-1) 的矩形区域和。

计算公式为： dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1]

查询区域和公式为： Sum(x1, y1, x2, y2) = dp[x2+1][y2+1] - dp[x1][y2+1] - dp[x2+1][y1] + dp[x1][y1]

注意下标的映射关系，这是本题最容易出错的地方。

C++ 实现

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        // 构建 (m+1) x (n+1) 的前缀和矩阵，方便处理边界
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        
        // 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. 计算结果矩阵
        vector<vector<int>> ret(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // 计算区域边界，注意 +1 是为了适配 dp 表的下标
                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;
    }
}

时间复杂度：O(mn)，空间复杂度：O(mn)。