LeetCode算法日记 - Day 16: 连续数组、矩阵区域和
目录
1. 连续数组
1.1 题目解析
1.3 代码实现
1.4 总结
2. 矩阵区域和
2.1 题目解析
2.2 解法
2.3 代码实现
1. 连续数组
525. 连续数组 - 力扣（LeetCode）
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
示例 1：
输入：nums = [0,1] 输出：2 说明：[0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2：
输入：nums = [0,1,0] 输出：2 说明：[0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。
示例 3：
输入：nums = [0,1,1,1,1,1,0,0,0] 输出：6 解释：[1,1,1,0,0,0] 是具有相同数量 0 和 1 的最长连续子数组。
提示：
1 <= nums.length <= 105nums[i]不是0就是1
1.1 题目解析
本题要求：找到一个最长的连续子数组，里面 0 和 1 的数量相同。
等价转化：把 0 看作 -1，把 1 看作 +1，那么问题就变成 找一个和为 0 的最长子数组。
常规解法
最直观的想法是：
-
枚举所有子数组 [i, j]
-
检查 0 和 1 的数量是否相等。
但这样需要两重循环计算子数组和，时间复杂度 O(n²)，数组长度可达 10^5，必然超时。
问题分析
想高效求解“子数组和 = 0”，需要快速判断某一段的和。
这就是典型的 前缀和问题，为了快速找到前缀和是否出现过，我们用 哈希表 存储：
-
key = 前缀和
-
value = 第一次出现该前缀和的位置
这样一旦在 i 位置再次遇到相同的 sum，说明 i - hash.get(sum[i])这段子数组和为 0。
并且我们只记录“第一次出现的位置”，才能保证子数组最长
1.2 解法
i）将 0 转换为 -1，把问题转为“寻找最长和为 0 的子数组”。
ii）使用 sum 代替数组
iii）手动放入 0:-1 确保结果不被遗漏
iiii）用 前缀和 + 哈希表 记录第一次出现的前缀和位置。
iiiii）每次遇到相同的前缀和，就更新最大长度。
iiiiii）公式：
-
sum += (nums[i] == 0 ? -1 : 1)
-
若 sum[i] 曾经出现过：
maxLen = max(maxLen, i - hash.get(sum[i]))
1.3 代码实现
class Solution {public int findMaxLength(int[] nums) {Map<Integer, Integer> hash = new HashMap<>();hash.put(0, -1); // 前缀和为0，默认出现在-1位置int sum = 0, ret = 0;for (int i = 0; i < nums.length; i++) {// 0 记作 -1，1 记作 +1sum += (nums[i] == 0 ? -1 : 1);if (hash.containsKey(sum)) {// 更新最长子数组长度ret = Math.max(ret, i - hash.get(sum));} else {// 只记录第一次出现的位置hash.put(sum, i);}}return ret;}
}
1.4 总结
前缀和 + HashMap 初始化总结
| 类型 | 典型题目 | 初始化 | 为什么这样做 | 如果不这样会怎样 |
|---|---|---|---|---|
| 统计区间个数 （有多少个子数组满足条件） | - 和为 K 的子数组- subarraysDivByK | hash.put(0, 1) | 把「空区间」当成一种可能。假设在下标 -1 时前缀和=0 出现过一次。这样当 [0..i] 整段刚好满足 时，不会漏掉。 | - 如果不设：第一个符合条件的子数组（从下标 0 开始）会漏掉。- 如果设成 0:0：第一个符合条件的子数组不会被统计到。 |
| 求最长区间长度 （最长的满足条件子数组） | - 连续数组 (Contiguous Array)- 0 和 1 数量相等的最长子数组 | hash.put(0,-1) | 记录「最早出现该前缀和的位置」。设为 -1 意味着在数组左边虚拟一个位置。这样当 [0..i] 整段满足条件 时，长度能算成 i - (-1) = i+1。 | - 如果不设：当整段 [0..i] 符合条件时，长度算不出来。- 如果设成 0:0：长度会少 1。 |
| 其他变种 （最短区间 / 特殊条件） | - 具体题目要具体分析 | 一般也需要「虚拟起点」 | 只要本质是“依赖前缀和的差值”，就可能要加初始化 | 初始化不当 → 可能漏掉 最左端区间，或导致答案长度 / 个数偏差 |
记忆技巧（通俗版）
-
统计“有多少个” →
0:1
想象你在数东西：「空篮子」也算 1 个可能，这样第一个东西放进来时就能匹配成功，不会漏掉。 -
统计“最长长度” →
0:-1
想象你要量尺子：「在起点左边-1 有个刻度 0」，这样从最左边开始到当前位置就能量出正确的长度。
如果你非要从 0 开始量，就会比真实少 1 格，x-0 代表的是偏移量，x- (-1) 则代表举例起点有多长，可以理解为一个是求偏移量，一个是求长度。
2. 矩阵区域和
1314. 矩阵区域和 - 力扣（LeetCode）
给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：
i - k <= r <= i + k,j - k <= c <= j + k且(r, c)在矩阵内。
示例 1：
输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1 输出：[[12,21,16],[27,45,33],[24,39,28]]
示例 2：
输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2 输出：[[45,45,45],[45,45,45],[45,45,45]]
提示：
m == mat.lengthn == mat[i].length1 <= m, n, k <= 1001 <= mat[i][j] <= 100
2.1 题目解析
给你一个二维矩阵 mat，对每个元素 (i,j)，求其周围 k 范围内的矩阵元素和（包括自己）。本质是多次二维区间求和问题。
常规解法
最直观的做法是，对每个 (i,j) 遍历其周围 (r,c) 范围，累加和。
-
对每个元素遍历 (2k+1)^2 个格子，矩阵大小 m*n，复杂度约 O(m*n*k^2)。
-
当 m,n,k 最大 100 时，最坏 100*100*100*100=10^8，会超时。
思路转折
要想高效 → 必须预处理 → 使用二维前缀和。
-
预处理后，每个元素的区域和可以在 O(1) 时间内计算。
-
关键是确定每个元素的「左上角」和「右下角」坐标，并映射到前缀和矩阵。
-
注意越界处理：左上角 x1 = max(0,i-k)，右下角 x2 = min(m-1,i+k)，列同理。
2.2 解法
-
构建二维前缀和矩阵 dp，dp[i][j] 表示 mat[0..i-1][0..j-1] 的元素和。
-
任意子矩阵 (x1,y1) 到 (x2,y2) 的和
sum = dp[x2+1][y2+1] - dp[x1][y2+1] - dp[x2+1][y1] + dp[x1][y1]
i）预处理前缀和矩阵 dp，大小 (m+1)x(n+1)，第一行第一列为 0。
ii）对每个元素 (i,j)
-
计算 block 左上角 (x1,y1) = (max(0,i-k), max(0,j-k))
-
计算 block 右下角 (x2,y2) = (min(m-1,i+k), min(n-1,j+k))
-
利用前缀和公式得到区域和，赋值给 answer[i][j]
2.3 代码实现
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. 计算每个元素的 block sumint[][] answer = 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);int y1 = Math.max(0, j-k);int x2 = Math.min(m-1, i+k);int y2 = Math.min(n-1, j+k);answer[i][j] = dp[x2+1][y2+1] - dp[x1][y2+1] - dp[x2+1][y1] + dp[x1][y1];}}return answer;}
}