LeetCode 525. 连续数组
目录
题目描述
题意分析
给定一个只含 0 和 1 的二进制数组，要找出含有相同数量的 0 和 1 的最长连续子数组，返回它的长度。答案只要长度，不要位置，所以不必记录起点。
「数量相同」这个条件不方便直接维护——它牵涉两个计数器，判定要做一次减法比较，而且区间与区间之间没有可复用的结构。真正的突破口是把它换一种度量方式：把每个 0 记作
-1，每个 1 记作+1。这样一来，「区间内 0 和 1 的个数相等」就精确地等价于「这个区间的元素之和为 0」。原问题于是变成一道标准题：在一个只含 ±1 的数组里，求和为 0 的最长子数组。这一步转换是整道题的全部难点，转换完成后剩下的都是套路。之所以说这是「换度量」而不是「小技巧」，是因为它把两个耦合的计数器压成了一个标量。这个标量可以做前缀，可以相减，可以进哈希表——所有前缀和的工具立刻全部可用，而两个计数器是做不到的。
约束方面，数组长度上限 $10^5$，说明 $O(n^2)$ 的枚举（$10^{10}$）超时，目标是 $O(n)$ 或 $O(n \log n)$。元素只有 0 和 1 两种取值，意味着相邻两项的差值只能是
+1或-1，也就是这个标量的变化是逐步连续的，不会跳跃——这一点在写代码时用不上，但能帮助理解为什么它的取值范围只有[-n, n]。边界情形：可能不存在任何合法子数组（如
nums = [1]或全 1 数组），此时返回 0；答案可能是整个数组（如nums = [0, 1]）；答案一定是偶数长度，因为 0 和 1 各占一半；数组长度为 1 时必然返回 0。
解法：前缀和 + 最早位置哈希表
核心思路
把
0视为-1，把1视为+1。这样「0 和 1 数量相同」就等价于「区间和为 0」。遍历到下标
i时，用balance表示截至当前位置「1 的数量减 0 的数量」，并把数组开头之前的虚拟位置-1视为状态 0。区间(j, i]平衡，当且仅当位置j与位置i的balance相同。因此遍历到右端点时，只需查找当前状态是否曾出现。题目求最长区间，所以哈希表保存每个
balance的最早位置，命中后不能覆盖。初始化0 -> -1后，从下标 0 开始的合法区间也能统一按i - first[balance]计算。正确性：任意合法区间的左右前缀状态必然相同；当算法走到该区间右端点时，一定能查到这个状态。对固定右端点，状态出现得越早，区间越长，所以保留首次位置不会漏掉更优答案。
解题步骤
- 建立哈希表
first，先写入0 -> -1。- 从左到右遍历：遇到 1 令
balance++，遇到 0 令balance--。- 若当前
balance已出现，用当前位置减去首次位置更新最长长度。- 若未出现，记录当前位置；后续再次出现时不覆盖。
- 遍历结束返回最大长度，无合法区间时初值 0 就是答案。
例如
nums = [0, 1, 0]：balance依次为-1、0、-1。位置 1 的状态 0 命中初始位置-1，得到长度 2；位置 2 的状态-1命中首次位置 0，又得到长度 2。答案为 2。
代码实现
import java.util.HashMap;
import java.util.Map;
class Solution {
public int findMaxLength(int[] nums) {
Map<Integer, Integer> first = new HashMap<>();
first.put(0, -1);
int balance = 0;
int ans = 0;
for (int i = 0; i < nums.length; i++) {
balance += nums[i] == 1 ? 1 : -1;
Integer index = first.get(balance);
if (index != null) {
ans = Math.max(ans, i - index);
} else {
first.put(balance, i);
}
}
return ans;
}
}
func findMaxLength(nums []int) int {
first := map[int]int{0: -1}
balance, ans := 0, 0
for i, num := range nums {
if num == 1 {
balance++
} else {
balance--
}
if index, ok := first[balance]; ok {
if i-index > ans {
ans = i - index
}
} else {
first[balance] = i
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$。数组只遍历一次，哈希表查询和写入的均摊时间为 $O(1)$。
- 空间复杂度：$O(n)$。最坏情况下会记录 $n + 1$ 个不同的前缀状态。
关键点总结
- 把 0 映射成
-1，将数量相等转换为区间和为 0。- 两个相等的前缀状态之间必然是一段平衡区间。
- 求最长要保存首次位置；若求最短，记账策略才会不同。
0 -> -1消除了「合法区间从下标 0 开始」的特判。- 面试表达链路：等量关系转零和 → 相同前缀定位区间 → 最早位置保证最长。
易错点总结
- 覆盖首次位置：
[0, 1, 0, 0, 1, 1]中状态 0 多次出现；覆盖后会丢掉从开头形成的长度 6。- 遗漏
0 -> -1：[0, 1]会被错误地算成无解。- 长度多加 1：表中保存的是区间左端点的前一个位置，公式应为
i - index。- 把 0 当作 0 累加：此时前缀只统计 1 的数量，已不再表示两类元素的数量差。
- 用出现次数代替首次下标：出现次数适合统计合法区间个数，无法计算最长长度。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| LCR 011. 连续数组 | 中等 | 与本题同题异名，代码可直接照搬，适合用来复查初始项与长度公式 |
| 面试题 17.05. 字母与数字 | 中等 | 把 0/1 换成字母与数字两类字符，且要求返回子数组本身，需额外记录最优起点 |
| 325. 和等于 k 的最长子数组长度 | 中等 | 目标和从固定的 0 推广到任意 k，查询键变成 prefix - k，是本题的一般形式 |
| 560. 和为 K 的子数组 | 中等 | 求区间个数而非最长长度，哈希表要存出现次数并累加，记账目标完全不同 |
| LCR 010. 和为 K 的子数组 | 中等 | 与 560 同题异名，可用来对照「存次数」与「存首次下标」两种记账的差别 |
| 974. 和可被 K 整除的子数组 | 中等 | 判据换成前缀和同余，哈希键改为取模结果，还要处理负数取模的修正 |
| 1074. 元素和为目标值的子矩阵数量 | 困难 | 二维版本，先按行压缩降维，内层再套一遍前缀和加哈希的计数 |
| 1234. 替换子串得到平衡字符串 | 中等 | 同样追求四类字符的数量平衡，但改为求最短替换窗口，用滑动窗口而非哈希表 |