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

Java 实现

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

032 矩阵区域和

题目链接：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) 在矩阵内。

算法思路：二维前缀和

这是一道典型的二维前缀和应用题。核心在于快速计算任意矩形区域的和。

假设我们有一个二维前缀和数组 dp，其中 dp[i][j] 表示原矩阵中从 (0, 0) 到 (i-1, j-1) 的矩形区域和（为了方便处理边界，dp 通常比原矩阵多一行一列）。

对于目标位置 (i, j)，我们需要计算的区域是以 (i, j) 为中心，半径为 k 的正方形区域。确定该区域的左上角 (x1, y1) 和右下角 (x2, y2) 坐标是关键：

1. 左上角坐标：

   • 理论值：x1 = i - k, y1 = j - k
   • 修正值：由于不能小于 0，取 max(0, i - k) 和 max(0, j - k)。
   • 映射到 dp 表：因为 dp 有偏移，实际访问需 +1，即 x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1。

2. 右下角坐标：

   • 理论值：x2 = i + k, y2 = j + k
   • 修正值：由于不能超过矩阵边界 (m-1, n-1)，取 min(m - 1, i + k) 和 min(n - 1, j + k)。
   • 映射到 dp 表：同样 +1，即 x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1。

利用容斥原理计算区域和： Area = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]

时间复杂度为 O(m * n)，空间复杂度为 O(m * n)。

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) {
                // 计算区域边界，注意 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;
    }
};

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. 计算结果
        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;
    }
}

总结

这两道题是前缀和算法的经典应用。第一题通过一维前缀和配合哈希表解决了一维区间问题，关键在于将 0 转换为 -1 使问题转化为求和为 0；第二题则是二维前缀和的基础应用，重点在于处理边界条件和坐标映射。掌握这两种模式，可以应对大量涉及区间查询的问题。