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

Java 实现

class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> hash = new HashMap<>();
        // 默认存在一个前缀和为 0 的情况，对应下标 -1
        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)，哈希表在最坏情况下需要存储 n 个不同的前缀和。

032 矩阵区域和

问题描述： 给定一个 m x n 的矩阵 mat 和一个整数 k，返回一个新的矩阵 answer，其中 answer[i][j] 等于原矩阵中以 (i, j) 为中心、边长为 2k+1 的正方形区域内的元素之和。

思路分析

这是一道典型的二维前缀和应用题。直接对每个点暴力求和会导致 O(mnk²) 的复杂度，利用二维前缀和可以将查询优化至 O(1)。

定义 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]

对于任意目标点 (i, j)，我们需要确定其对应的左上角 (x1, y1) 和右下角 (x2, y2)。由于可能超出矩阵边界，需要进行截断处理：

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

最后利用容斥原理计算区域和： Sum = 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));
        
        // 预处理前缀和矩阵
        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];
            }
        }
        
        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, y1 = max(0, j - k) + 1;
                int x2 = min(m - 1, i + k) + 1, 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, y1 = Math.max(0, j - k) + 1;
                int x2 = Math.min(m - 1, i + k) + 1, 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(m * n)，需遍历矩阵两次（一次构建前缀和，一次计算结果）。
• 空间复杂度：O(m * n)，用于存储前缀和矩阵。

这两道题的核心都在于如何将问题转化为前缀和问题。第一题通过数值转换将计数问题变为求和问题，第二题则是标准的二维前缀和模板应用。建议在实际编码时多画图辅助理解坐标映射关系，尤其是边界条件的处理。