前缀和算法详解：连续数组与矩阵区域和

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

1.3.2 Java 实现

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

题目描述：

2.1 算法思路：二维前缀和

二维前缀和的简单应用题，关键就是我们在填写结果矩阵的时候，要找到原矩阵对应区域的【左上角】以及【右下角】的坐标。

（1）左上角坐标：x1 = i - k，y1 = j - k，但是由于会「超过矩阵」的范围，因此需要对 0 取一个 max。因此修正后的坐标为：x1 = max(0, i - k)，y1 = max(0, j - k)；

（2）右下角坐标：x2 = i + k，y2 = j + k，但是由于会【超过矩阵】的范围，因此需要对 m - 1，以及 n - 1 取一个 min。因此修正后的坐标为：x2 = min(m - 1, i + k)，y2 = min(n - 1, j + k)。

然后将求出来的坐标代入到【二维前缀和矩阵】的计算公式上即可，注意下标的映射关系。

2.2 算法实现

2.2.1 C++ 实现

class Solution { 
public: 
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) { 
        int m = mat.size(), n = mat[0].size(); // 行和列 
        // 1、预处理一个前缀和矩阵 
        vector<vector<int>> dp(m + 1, vector<int>(n + 1)); // 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、使用前缀和矩阵 
        vector<vector<int>> ret(m, vector<int>(n)); // 跟原始矩阵同等规模 
        for(int i = 0; i < m; i++) 
            for(int j = 0; j < n; j++) { 
                int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1; // +1 就是为了在 dp 表里面直接可以找到 
                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; 
    } 
};

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

2.2.2 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(mn)，空间复杂度：O(mn)。