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

031 连续数组

题目链接：525. 连续数组

题目描述： 给定一个二进制数组 nums，找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

解法一：暴力解法

暴力解法是枚举所有可能的子数组，统计其中 0 和 1 的数量是否相等。这种方法的时间复杂度为 O(n^3) 或 O(n^2)，在数据量较大时容易超时，因此不推荐。

解法二：前缀和 + 哈希表

这道题的关键在于转化思路。如果我们将数组中的 0 视为 -1，1 保持不变，那么问题就转化为：寻找最长的子数组，使得其元素之和为 0。

设 sum[i] 表示从索引 0 到 i 的前缀和。如果存在两个索引 j < i，使得 sum[j] == sum[i]，那么区间 (j, i] 内的元素之和必然为 0。为了找到最长子数组，我们需要记录每个前缀和第一次出现的位置。

具体步骤如下：

1. 初始化一个哈希表，用于存储前缀和及其首次出现的下标。初始状态存入 {0: -1}，表示前缀和为 0 出现在索引 -1 处（虚拟边界）。
2. 遍历数组，累加当前前缀和。将 0 视为 -1，1 视为 1。
3. 检查当前前缀和是否已存在于哈希表中：
   • 若存在，说明找到了一个和为 0 的区间，更新最大长度 max_len = max(max_len, i - hash[sum])。
   • 若不存在，将当前前缀和及索引存入哈希表。
4. 遍历结束后返回最大长度。

注意：空间复杂度为 O(n)，因为最坏情况下需要存储 n 个不同的前缀和。

C++ 实现

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> hash;
        // 初始化前缀和为 0 的位置为 -1
        hash[0] = -1;
        
        int sum = 0;
        int ret = 0;
        
        for (int i = 0; i < nums.size(); ++i) {
            // 0 记为 -1，1 记为 1
            sum += (nums[i] == 0 ? -1 : 1);
            
            if (hash.count(sum)) {
                // 如果之前出现过相同的前缀和，计算区间长度
                ret = max(ret, i - hash[sum]);
            } else {
                // 只记录第一次出现的位置
                hash[sum] = i;
            }
        }
        return ret;
    }
};

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；第二题则是二维前缀和的基础应用，重点在于处理边界条件和坐标映射。掌握这两种模式，可以应对大量涉及区间查询的问题。