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

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

031 连续数组

题目链接： 525. 连续数组

问题描述

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

解题思路

暴力枚举所有子数组的时间复杂度为 O(n²)，在数据量较大时容易超时。我们可以利用前缀和结合哈希表将时间复杂度优化至 O(n)。

核心转化思想如下：

1. 如果将数组中的 0 记为 -1，1 记为 1，那么问题就转化为寻找一段区间，其元素之和等于 0。
2. 设 sum[i] 表示从索引 0 到 i 的前缀和。若存在两个位置 i 和 j（假设 i < j），使得 sum[j] - sum[i] = 0，即 sum[j] == sum[i]，则说明区间 [i+1, j] 内的元素和为 0。
3. 为了得到最长子数组，我们需要记录每个前缀和第一次出现的位置。当再次遇到相同的前缀和时，用当前位置减去首次出现的位置即可得到长度。

代码实现

C++ 实现

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> hash;
        // 初始化前缀和为 0 的位置为 -1，处理从索引 0 开始的子数组
        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;
    }
}

复杂度分析

• 时间复杂度： O(n)，其中 n 是数组长度。我们只需遍历一次数组。
• 空间复杂度： O(n)，哈希表在最坏情况下需要存储 n 个不同的前缀和。

---

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

解题思路

这是一个典型的二维前缀和应用题。直接计算每个点的区域和会导致重复计算，时间复杂度较高。通过预处理构建二维前缀和数组，可以在 O(1) 时间内计算出任意矩形区域的和。

关键步骤在于确定目标矩形的左上角和右下角坐标，并进行边界检查：

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

注意：由于前缀和数组通常多开一行一列以简化边界处理，实际查询时需进行下标映射调整。

代码实现

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) 的前缀和数组，dp[i][j] 表示左上角 (0,0) 到 (i-1,j-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 数组下标偏移 +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;
    }
};

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;
    }
}

复杂度分析

• 时间复杂度： O(m * n)，其中 m 和 n 分别为矩阵的行数和列数。我们需要遍历整个矩阵两次（一次构建前缀和，一次生成结果）。
• 空间复杂度： O(m * n)，用于存储二维前缀和数组。

---

总结

这两道题展示了前缀和在不同维度下的应用技巧。一维场景下配合哈希表可以解决子数组求和问题，而二维场景下则需要构建二维前缀和矩阵来快速响应区域查询。掌握这种'预处理 + 公式计算'的模式，能显著提升处理范围统计类问题的效率。