LeetCode LCR 011. 连续数组
题目描述
题意分析
数组只含零和一，求其中零与一数量相同的最长连续子数组长度。要求连续，不能挑选不相邻元素；找不到这样的非空区间时返回零。
合法区间的两类数量相同，因此长度一定为偶数，但只检查长度为偶数并不够，还需要准确判断两类数量是否平衡。
解法：前缀平衡值与最早位置
核心思路
[!blue]
将一视为
+1，零视为-1，区间累计值就等于一的个数减去零的个数。两类数量相同，恰好等价于这个区间和为零；只需在扫描时这样计分，不必真的修改输入数组。用
s保存已扫描前缀的平衡值。若结束于下标j和结束于当前下标i的两个前缀值相同，那么它们之间的区间nums[j+1..i]平衡值为零，长度为i - j。对固定的当前右端，同值历史前缀越早出现，得到的区间就越长。因此哈希表
d只保存每个平衡值第一次出现的位置。再次遇到相同值时，用它计算长度即可，不覆盖原位置；后来的同值位置对于任何未来右端都不可能更优。初始化
d[0] = -1，表示第一个元素之前的空前缀。如果当前整个前缀平衡，长度就统一算成i - (-1)，自然覆盖从下标零开始的答案。每个右端都与相同平衡值的最早位置配对，得到这个右端下最长的合法候选，再取全局最大值。映射中有正负贡献，普通窗口不能依据和的大小单调收缩，而前缀相等关系不受这个影响。
解题步骤
- 初始化平衡值和答案为零，记录空前缀
d[0] = -1。- 从左到右扫描，一使平衡值加一，零使平衡值减一。
- 若当前平衡值已有记录，用当前下标减去最早下标更新最大长度。
- 若未出现过，记录当前下标作为它的首次位置。
- 扫描结束后返回答案，未命中时自然保持零。
代码实现
class Solution {
public int findMaxLength(int[] nums) {
Map<Integer, Integer> d = new HashMap<>();
// 空前缀：和为 0，虚拟下标 -1，使「从头开始」的区间长度算作 i - (-1)。
d.put(0, -1);
int answer = 0;
int s = 0;
for (int i = 0; i < nums.length; ++i) {
// 0 记 -1、1 记 +1，「数量相同」就变成「区间和为 0」。
s += nums[i] == 0 ? -1 : 1;
if (d.containsKey(s)) {
answer = Math.max(answer, i - d.get(s));
} else {
// 只记最早出现的位置，越靠左区间越长。
d.put(s, i);
}
}
return answer;
}
}
func findMaxLength(nums []int) (answer int) {
d := map[int]int{0: -1}
s := 0
for i, x := range nums {
if x == 1 {
s++
} else {
s--
}
if j, ok := d[s]; ok {
answer = max(answer, i-j)
} else {
d[s] = i
}
}
return
}
复杂度分析
设数组长度为 $n$。
- 时间复杂度：期望 $O(n)$，每个位置进行常数次哈希操作。
- 辅助空间复杂度：$O(n)$，至多记录 $n+1$ 种平衡值的首次位置。
关键点总结
[!green]
- 零记负一、一记正一，把数量平衡转换为区间和为零。
- 相等前缀之间的区间合法，求最长就始终保留最早位置。
- 空前缀在虚拟下标负一，长度统一为两个前缀下标之差。
易错点总结
[!yellow]
- 仍把零当成数值零累加，得到的只是一个数的数量，不能表示两类平衡。
- 空前缀位置写成零，会使从数组开头开始的区间少算一个元素。
- 长度已经是
i - d[s]，不要再加一，因为记录的是左端之前的位置。- 覆盖为较晚的相同平衡值位置，会缩短后续候选，漏掉最长答案。
- 本题保存最早位置而不是频次；频次只能回答数量，不能直接给出最远距离。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 560. 和为 K 的子数组 | 中等 | 把0改成-1后，0与1等量等价于区间和为0；本题保存最早前缀位置求最长长度，而非统计数量。 |
| 1124. 表现良好的最长时间段 | 中等 | 同样把两类元素映射成正负贡献，原题要求区间和严格为正，本题要求等于0。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！