525. 连续数组
题目描述
输入只含 0 和 1 的数组 nums。
在所有 0 的个数与 1 的个数相等的连续子数组中，找出最长的一个，返回它的长度。不存在这样的子数组时返回 0。
示例 1
输入：nums = [0,1] 输出：2
解释：整个数组含一个 0 和一个 1。
示例 2
输入：nums = [0,1,0] 输出：2
解释：[0,1] 或 [1,0] 都满足，长度为 2。
示例 3
输入：nums = [0,1,1,1,1,1,0,0,0] 输出：6
解释：[1,1,1,0,0,0] 含三个 0 和三个 1，长度为 6。
数据范围
1 <= nums.length <= 10^5nums[i]只会是0或1。
解题思路
把 0 看成 -1，“0 和 1 一样多”就变成“子数组和为 0”。用 bal 表示前缀中 1 的个数减 0 的个数，若两个位置的 bal 相同，它们之间的子数组就是平衡的。用哈希表记录每个 bal 最早出现的下标（空前缀 bal=0 记在 -1），每次遇到已出现的 bal 就用 i - first[bal] 更新最长长度。
为什么正确
first[b] 是已扫描前缀中 bal 等于 b 的最小下标；best 是以已扫描位置结尾的最长平衡子数组长度。
复杂度分析
时间 O(n)，空间 O(n)。
易错点
已经出现过的 bal 不要用新下标覆盖：要的是最长子数组，所以左端点越早越好。忘记放入 {0: -1} 会漏掉从下标 0 开始的子数组。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
first = {0: -1}
bal = best = 0
for i, x in enumerate(nums):
bal += 1 if x == 1 else -1
if bal in first:
best = max(best, i - first[bal])
else:
first[bal] = i
return bestclass Solution {
public int findMaxLength(int[] nums) {
Map<Integer, Integer> first = new HashMap<>();
first.put(0, -1);
int bal = 0, best = 0;
for (int i = 0; i < nums.length; i++) {
bal += nums[i] == 1 ? 1 : -1;
if (first.containsKey(bal)) {
best = Math.max(best, i - first.get(bal));
} else {
first.put(bal, i);
}
}
return best;
}
}class Solution {
public:
int findMaxLength(vector<int>& nums) {
unordered_map<int, int> first;
first[0] = -1;
int bal = 0, best = 0;
for (int i = 0; i < (int)nums.size(); i++) {
bal += nums[i] == 1 ? 1 : -1;
if (first.count(bal)) {
best = max(best, i - first[bal]);
} else {
first[bal] = i;
}
}
return best;
}
};func findMaxLength(nums []int) int {
first := map[int]int{0: -1}
bal, best := 0, 0
for i, x := range nums {
if x == 1 {
bal++
} else {
bal--
}
if j, ok := first[bal]; ok {
if i-j > best {
best = i - j
}
} else {
first[bal] = i
}
}
return best
}var findMaxLength = function(nums) {
const first = new Map([[0, -1]]);
let bal = 0, best = 0;
for (let i = 0; i < nums.length; i++) {
bal += nums[i] === 1 ? 1 : -1;
if (first.has(bal)) {
best = Math.max(best, i - first.get(bal));
} else {
first.set(bal, i);
}
}
return best;
};function findMaxLength(nums: number[]): number {
const first = new Map<number, number>([[0, -1]]);
let bal = 0, best = 0;
for (let i = 0; i < nums.length; i++) {
bal += nums[i] === 1 ? 1 : -1;
if (first.has(bal)) {
best = Math.max(best, i - first.get(bal)!);
} else {
first.set(bal, i);
}
}
return best;
}