LeetCode LCR 011. 连续数组

2026-03-28 HGNULB 约 8 分钟

文章信息 5 个分类 4 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 011. 连续数组

题意分析

给一个只含 $0$ 和 $1$ 的二进制数组 nums，找出含有相同数量的 $0$ 和 $1$ 的最长连续子数组，返回它的长度。

要求的是最长长度，说明我们关心的是区间两端离得多远，而不是区间里的具体内容。数据规模 $n \le 10^5$，$O(n^2)$ 的区间枚举约 $10^{10}$ 次，必然超时，目标是 $O(n)$。

「$0$ 和 $1$ 数量相同」这个条件初看不像是区间和的形式，但只要把 $0$ 记作 $-1$、$1$ 记作 $+1$，「数量相同」就等价于「区间和为 $0$」。这一步映射是全题的枢纽：它把一个计数条件翻译成了标准的「和为定值的子数组」问题。

完成映射后，元素变成了 $\pm 1$，也就是有负数。这直接排除了滑动窗口——区间和不再随扩张单调，收缩判据失效。剩下的通用工具是前缀和：区间和为 $0$ 等价于两端的前缀和相等，于是问题变成「找两个相等的前缀和，且下标相距最远」。

边界方面：可能不存在任何合法子数组（例如全是 $1$），此时应返回 $0$；合法子数组的长度必然是偶数；最长解可能就是整个数组，因此必须让「从下标 $0$ 开始」的区间也能被算到，这要求引入一个代表空前缀的初始项。

解法：前缀和维护区间信息

核心思路

暴力做法是枚举所有区间，统计里面 $0$ 和 $1$ 的个数是否相等，$O(n^2)$ 起步。瓶颈在于：每个区间都从零开始重新数，而相邻区间之间其实只差一个元素。

第一次转化是把计数变成求和：令 $0 \mapsto -1$、$1 \mapsto +1$，那么一个区间里 $0$ 与 $1$ 的个数相等，当且仅当这个区间的映射后元素之和为 $0$。

第二次转化是把区间和变成前缀和之差：令 $s_i$ 为映射后前 $i+1$ 个元素之和，并约定空前缀 $s_{-1} = 0$。区间 nums[i..j] 合法当且仅当 $s_j - s_{i-1} = 0$，即 $s_j = s_{i-1}$。于是问题彻底变成：在前缀和序列中找两个相等的值，使它们的下标相距最远。

由此确定要维护的状态：哈希表 d 把每个出现过的前缀和值映射到它第一次出现的下标。为什么只存第一次？因为对固定的右端点，前缀和相等的左端点越靠左，得到的区间越长；后来出现的同值下标只会给出更短的区间，记下来毫无用处。这条「只记最早」正是本题与「和为 K 的子数组」（那里记的是出现次数）最本质的差别——问什么，哈希表就存什么。

不变量是：扫描到下标 i 时，d 中保存的是所有在 i 之前（含空前缀）出现过的前缀和值各自的最早下标；answer 是仅由这些信息能确定的最长合法区间长度。每步先算出新的前缀和 s，若 d 里已有这个值就用 i - d[s] 更新答案，否则把 s 的最早下标记为 i。两个分支互斥，因为一旦记录就不再覆盖。

空前缀的初始项写作 d[0] = -1。下标取 $-1$ 而不是 $0$，是因为空前缀在「第一个元素之前」的位置；这样当 $s_j = 0$ 时，区间长度算作 $j - (-1) = j + 1$，恰好是从开头到 j 的完整长度。

解题步骤

初始化 d = {0: -1}。键 $0$ 是空前缀的和，值 $-1$ 是它的虚拟下标。缺了这一项，所有以下标 $0$ 为左端的答案都会丢失；下标写成 $0$ 则每个这样的答案都会少算一格。

s = 0、answer = 0，按下标顺序遍历。答案初值 $0$ 同时也是「无解」时的正确返回值，不需要额外特判。

每步先做映射并累加：遇到 $1$ 就 s++，遇到 $0$ 就 s--。这一步把「计数相等」实时转成「和为零」。

若 d 中已有键 s，用 i - d[s] 更新答案。区间是左开右闭的 (d[s], i]，长度恰好是下标之差，不需要 +1——因为 d[s] 记的是左端点的前一个位置。

否则才写入 d[s] = i。必须是 else 分支：一旦覆盖成更靠右的下标，后续能得到的区间就变短了，答案会偏小。

每个前缀和值只写一次，因此哈希表规模不超过前缀和的取值个数，即 $O(n)$。

循环结束返回 answer，无需后处理。

以 nums = [0, 1, 0] 走一遍，期望答案 2。初始 d = {0: -1}、s = 0、answer = 0。i = 0，元素是 $0$：s = -1；d 中没有键 $-1$，写入 d[-1] = 0。i = 1，元素是 $1$：s = 0；d 中有键 $0$，值是 $-1$，更新 answer = max(0, 1 - (-1)) = 2——这个区间是 nums[0..1] = [0, 1]，正好一个 $0$ 一个 $1$；因为走的是「已存在」分支，d[0] 保持 $-1$ 不变。i = 2，元素是 $0$：s = -1；d 中有键 $-1$，值是 $0$，更新 answer = max(2, 2 - 0) = 2——对应区间 nums[1..2] = [1, 0]，同样合法但长度相同。返回 2。注意 i = 1 那一步如果覆盖了 d[0] = 1，那么当输入延长成 [0, 1, 1, 0] 时，最后一步会用 3 - 1 = 2 更新答案，而正确答案是 3 - (-1) = 4——这就是「只记最早」必须是 else 分支的直接原因。

代码实现

class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> d = new HashMap<>();
        // 空前缀：和为 0，虚拟下标 -1，使「从头开始」的区间长度算作 i - (-1)。
        d.put(0, -1);
        int answer = 0, 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
}

复杂度分析

时间复杂度：$O(n)$。数组只扫一遍，每个元素做一次加减、一次哈希查询，最多一次哈希写入，均摊都是常数。凭的是「相等前缀和」把区间枚举换成了一次查表。

空间复杂度：$O(n)$。哈希表存的是互不相同的前缀和值，数量不超过 $n + 1$。这份空间是必须的——元素含负数使窗口失效，就必须把全部历史前缀和的最早位置记下来。

关键点总结

把「两类元素数量相等」映射成 $\pm 1$ 求和，是这一族题的核心技巧；推广到「$0$ 的个数是 $1$ 的两倍」只需把权重换成 $+1$ 与 $-2$，思路完全不变。

区间和为 $0$ 等价于两端前缀和相等，这条等价把「找区间」降维成「找相等的两个值」，是前缀和最常用的形态之一。

哈希表存什么由问题问什么决定：求个数存出现次数（本题的姊妹题 LCR 010），求最长存最早下标（本题），求最短则存最近下标。定义一旦选定，写入策略（覆盖还是不覆盖）就随之确定。

空前缀项 d[0] = -1 里的 $-1$ 不是随手写的哨兵，它精确对应「第一个元素之前」的位置，使长度公式统一成 i - d[s] 而不需要分类讨论。

if / else 的互斥结构本身就是「只记最早」的实现方式，比先查再无条件写入更不容易出错。

面试视角：面试官会先看你能不能想到 $\pm 1$ 映射，这一步说不出来就基本卡死；想到之后必被追问「为什么哈希表存最早下标而不是次数」，标准回答是「本题求最长，左端点越靠左越好，同值的后续位置只会给出更短的区间」。能顺带指出「如果改成求子数组个数，就要改存出现次数」，说明你抓的是方法而不是模板。

易错点总结

错误写法：忘记 d.put(0, -1)。输入 [0, 1] 时 i = 1 处的 s = 0 在表里查不到，反而被写入，返回 0 而不是 2。

错误写法：初始项写成 d.put(0, 0)。输入 [0, 1] 会算出长度 1 - 0 = 1，返回 1 而不是 2，所有从开头起算的区间都少一格。

错误写法：无条件执行 d.put(s, i)（没有 else）。输入 [0, 1, 1, 0] 时 d[0] 在 i = 1 处被覆盖成 $1$，最后一步算出 3 - 1 = 2，返回 2 而不是 4。

错误写法：把长度算成 i - d.get(s) + 1。多算一格，输入 [0, 1] 会返回 3，超过数组长度。

错误写法：映射写成「$0$ 记 $0$、$1$ 记 $1$」直接求和。此时区间和为 $0$ 只意味着全是 $0$，输入 [0, 1] 会返回 1（对应子数组 [0]）而不是 2。

错误写法：哈希表改存出现次数（照搬 LCR 010 的写法）。次数无法还原位置，输入 [0, 1, 1, 0] 根本算不出长度，只能得到「有多少个合法区间」这个另一个问题的答案。

错误写法：用滑动窗口，靠「$0$ 比 $1$ 多就收缩左端」推进。输入 [1, 1, 0, 0, 1] 时窗口在 [1, 1, 0] 处判定不合法而收缩掉左端的 $1$，会漏掉正确答案 [1, 1, 0, 0]，返回值小于正确的 4。元素等价于 $\pm 1$，区间和不单调，窗口的收缩判据不成立。

错误写法：先构造完整前缀和数组，再双层枚举找相等的一对。逻辑对但复杂度 $O(n^2)$，$10^5$ 的数据必然超时。

相似题目

题目	难度	考察点
525. 连续数组	中等	与本题同题，可直接套用同一份 $\pm 1$ 映射
面试题 17.05. 字母与数字	中等	同样是 $\pm 1$ 平衡，但要返回具体子数组，且需处理多解取最左
325. 和等于 k 的最长子数组长度	中等	目标从 $0$ 换成任意 `k`，查的键变成 `s - k` 而非 `s`
560. 和为 K 的子数组	中等	求个数而非最长，哈希表改存出现次数并需「先查后写」
LCR 010. 和为 K 的子数组	中等	与 560 同题，是「存下标还是存次数」这一取舍的直接对照
974. 和可被 K 整除的子数组	中等	键换成前缀和的余数，负数取模要先加 `k` 再取模
1074. 元素和为目标值的子矩阵数量	困难	二维版本，需枚举上下边界压成一维后再套前缀和加哈希