LeetCode 面试题 17.05. 字母与数字

2022-04-05 HGNULB 约 13 分钟

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

分类

LeetCode CodeTop 中等未解决 2-5 字节跳动程序员面试金典（第 6 版）

题目描述

✅ 面试题 17.05. 字母与数字

题意分析

给一个只含字母和数字的字符数组，找出最长的连续子数组，要求其中字母的个数与数字的个数相等。返回这个子数组本身；若有多个等长的答案，返回起点最靠左的那个；若不存在，返回空数组。

要什么：一个子数组，不是长度。所以除了最大长度，还必须记住它的起点，最后按 [start, start + len) 切出来返回。

「连续」两个字排除了任意选取；「字母数等于数字数」是一个关于计数差的等式约束，而不是关于元素值的约束——具体是哪个字母、哪个数字完全无关紧要，只关心它属于两类中的哪一类。识别到这一点，输入就可以被压缩成一个只有两种取值的序列。

「返回最靠左的那个」这条要求决定了实现细节：在长度相等时不能更新答案，比较必须用严格大于。

约束透露的信号：数组长度可达 $10^5$。这个规模排除了 $O(n^2)$ 的枚举所有子数组（$10^{10}$），必须做到线性或准线性。而且这是一个「求满足某种和/计数等式的最长子数组」的问题，元素被映射成 $\pm 1$ 后有正有负，滑动窗口失效（窗口收缩时约束不具备单调性），标准工具是前缀和配哈希表。

边界：数组可能为空或全是字母/全是数字，此时答案是空数组，返回长度为 0 的数组而不是 null；答案的长度必然是偶数（两类各占一半）；数组元素是字符串，但每个字符串只需看首字符即可判定类别。

解法：前缀差值 + 哈希表

核心思路

先看暴力：枚举左端点 i 与右端点 j，统计 [i, j] 内两类元素的个数是否相等。即使用前缀和把统计降到 $O(1)$，枚举本身仍是 $O(n^2)$，$10^5$ 的规模下是 $10^{10}$ 次，必然超时。瓶颈在于：我们逐对检查了所有区间，而实际上「哪些区间合法」这件事有更强的结构可以利用。

第一步是把两类元素编码成数字。令字母记 $+1$、数字记 $-1$，定义前缀差值
\[\text{diff}(i) = \sum_{t=0}^{i} v_t, \qquad v_t = \begin{cases} +1 & \text{array}[t] \text{ 是字母} \\ -1 & \text{array}[t] \text{ 是数字} \end{cases}\]
那么子数组 [l, r] 内字母数与数字数相等，等价于这段区间的和为 0，也就是
\[\text{diff}(r) - \text{diff}(l-1) = 0 \iff \text{diff}(r) = \text{diff}(l-1)\]
这一步是全题的转折点：「区间内两类元素数量相等」被翻译成了「两个位置的前缀差值相同」。原本要检查一个区间的性质，现在只需比较两个标量。

于是问题变成：在前缀差值序列上，找一对相同的值，使得它们的下标相距最远。要让区间最长，对每个当前位置 r，应当去找值等于 diff(r) 的最早那个位置。所以用一张哈希表 first: 差值 → 该差值首次出现的下标，遍历时只在该差值尚未出现过时才写入，这样表中永远保存的是最早位置。

不变量是：在处理完下标 i 之后，对任意曾经出现过的差值 d，first[d] 等于 diff 首次取到 d 的那个下标。

还有一个必须预置的条目：first[0] = -1。它的含义是「在处理任何元素之前，前缀差值是 0，对应的虚拟下标是 -1」。有了它，以下标 0 开头的合法区间才能被正确识别——例如整个数组恰好合法时，diff(n-1) = 0，配对的起点是 first[0] = -1，算出长度 n - 1 - (-1) = n，起点 -1 + 1 = 0，完全正确。漏掉这一条会让所有从数组开头起算的答案全部丢失，是这类题最经典的错误。

长度与起点的换算要一次说清：若 first[diff] = start，则合法区间是 [start + 1, i]，长度为 i - start。注意这里 start 是配对位置本身（区间不含它），所以区间起点要加一、长度是下标之差而不是差加一——与常见的闭区间长度公式恰好相反，因为这里的两个端点一个是开的一个是闭的。

最后，因为要求多解取最靠左，更新答案时用 len > bestLen 而非 >=。由于我们总是与最早的同值位置配对，且 i 从左往右扫，第一次达到某个最大长度的方案自然就是起点最靠左的那个。

解题步骤

建哈希表 first 并预置 first.put(0, -1)；初始化 diff = 0、bestStart = 0、bestLen = 0。为什么要预置这一条：它代表「空前缀」的状态，是所有以下标 0 开头的合法区间能被找到的唯一依据。为什么 bestLen 初值是 0：不存在合法区间时答案就是空数组，0 既是长度下界也是正确的兜底值。

遍历下标 i，取 array[i] 的首字符判断类别，是数字则 diff--、否则 diff++。为什么只看首字符：题面保证每个元素是单个字母或单个数字组成的字符串，首字符已经足以定类。为什么用「是数字则减、否则加」而不是「是字母则加、否则减」：两种写法完全对称、结果一致，只要全程保持一致即可；关键是不能中途换标准。

若 diff 尚未在表中出现，则写入 first[diff] = i。为什么要判「尚未出现」：表的语义是「首次出现的位置」，无条件覆盖会把它变成「最近出现的位置」，配对出的区间就不是最长的了。

无论是否新写入，都取 start = first.get(diff) 并算 len = i - start。为什么可以统一处理：若 diff 是首次出现，start 恰好等于 i，算出 len = 0，不会误更新答案；这让「首次出现」与「重复出现」两种情形共用一条路径，省掉一个分支。

若 len > bestLen，更新 bestLen = len、bestStart = start + 1。为什么起点要加一：first[diff] = start 记录的是差值首次达到该值的位置，那个位置本身属于前缀而不属于答案区间，区间从 start + 1 开始。为什么用严格大于：长度相同时保留先找到的方案，满足「返回最靠左」的要求。

遍历结束后从 bestStart 起截取 bestLen 个元素返回。为什么 bestLen = 0 时也安全：截取长度为 0 会得到一个空数组，正是「不存在合法子数组」时该返回的结果，无需特判。

以 具体用例 array = ["A", "A", "1", "B", "2"] 走一遍，预期答案是 ["A", "1", "B", "2"]（下标 1 到 4，两个字母 A、B 与两个数字 1、2）。

初始化：first = {0: -1}，diff = 0，bestStart = 0，bestLen = 0。

i = 0（"A"，字母）：diff 变为 1。表中没有键 1，写入 first[1] = 0。取 start = 0，len = 0 - 0 = 0，不大于 bestLen = 0，不更新。
i = 1（"A"，字母）：diff 变为 2。写入 first[2] = 1。start = 1，len = 1 - 1 = 0，不更新。
i = 2（"1"，数字）：diff 变为 1。表中已有键 1（值为 0），不覆盖——这正是「只记首次出现」的关键时刻。取 start = first[1] = 0，len = 2 - 0 = 2 > 0，更新 bestLen = 2、bestStart = 0 + 1 = 1。此时的答案是下标 1 到 2，即 ["A", "1"]，一个字母配一个数字，正确。
i = 3（"B"，字母）：diff 变为 2。表中已有键 2（值为 1），不覆盖。start = 1，len = 3 - 1 = 2，不大于 bestLen = 2，不更新。这里体现了严格大于的作用：["A","1"]（起点 1）与 ["1","B"]（起点 2）等长，保留先找到的、起点更靠左的那个。
i = 4（"2"，数字）：diff 变为 1。表中已有键 1（值为 0），不覆盖。start = 0，len = 4 - 0 = 4 > 2，更新 bestLen = 4、bestStart = 1。

遍历结束，从下标 1 截取 4 个元素，得到 ["A", "1", "B", "2"]，与预期一致。

核对一下差值序列：diff 在下标 0 到 4 上依次是 1、2、1、2、1；最终配对的是下标 0 与下标 4（两处值都是 1），区间和为 diff(4) - diff(0) = 1 - 1 = 0。手工验证：下标 1 到 4 是 A、1、B、2，映射成 $+1, -1, +1, -1$，求和确实为 0，字母与数字各两个。

再看一个体现 first[0] = -1 价值的用例 array = ["A", "1"]：i = 0 时 diff = 1，写入 first[1] = 0，len = 0；i = 1 时 diff = 0，表中已有键 0（预置的 -1），start = -1，len = 1 - (-1) = 2 > 0，更新 bestLen = 2、bestStart = -1 + 1 = 0。返回整个数组，正确。若没有预置 first[0] = -1，i = 1 时会把 first[0] 写成 1、算出 len = 0，最终返回空数组——整整一个正确答案被漏掉。

代码实现

class Solution {
    // 记录每个前缀差值第一次出现的位置。
    public String[] findLongestSubarray(String[] array) {
        Map<Integer, Integer> first = new HashMap<>();
        first.put(0, -1);
        int diff = 0;
        int bestStart = 0;
        int bestLen = 0;

        for (int i = 0; i < array.length; i++) {
            char ch = array[i].charAt(0);
            if (Character.isDigit(ch)) {
                diff--;
            } else {
                diff++;
            }

            if (!first.containsKey(diff)) {
                first.put(diff, i);
            }

            int start = first.get(diff);
            int len = i - start;
            if (len > bestLen) {
                bestLen = len;
                bestStart = start + 1;
            }
        }

        String[] res = new String[bestLen];
        System.arraycopy(array, bestStart, res, 0, bestLen);
        return res;
    }
}

func findLongestSubarray(array []string) []string {
    // 记录每个前缀差值第一次出现的位置。
    first := make(map[int]int)
    first[0] = -1
    diff := 0
    bestStart := 0
    bestLen := 0

    for i := 0; i < len(array); i++ {
        ch := array[i][0]
        if ch >= '0' && ch <= '9' {
            diff--
        } else {
            diff++
        }

        if _, ok := first[diff]; !ok {
            first[diff] = i
        }

        start := first[diff]
        length := i - start
        if length > bestLen {
            bestLen = length
            bestStart = start + 1
        }
    }

    return array[bestStart : bestStart+bestLen]
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是数组长度。凭什么：只有一趟遍历，每个位置做一次字符判定、一次哈希查询、至多一次哈希插入和一次比较，全部均摊常数；末尾的截取是 $O(\text{bestLen})$，被 $O(n)$ 吸收。相比枚举所有区间的 $O(n^2)$，省下的正是「对每个右端点重新寻找左端点」的那层循环——哈希表把这个寻找过程压成了一次查表。

空间复杂度：$O(n)$。凭什么：哈希表最多存放 $n + 1$ 个不同的差值（差值的取值范围是 $[-n, n]$，但实际出现的种类不超过 $n+1$ 个，因为每步只变动 1）；返回的结果数组属于输出。理论上可以用一个长度 $2n+1$ 的数组代替哈希表（差值加上偏移量 $n$ 作下标），常数更小但空间量级不变。

关键点总结

「两类元素数量相等」要立刻翻译成「$\pm 1$ 映射后区间和为 0」。这是一个高频转换：把二元分类编码成 $+1$ 与 $-1$，计数的相等关系就变成了求和的归零关系，从而接入前缀和这套成熟工具。同理，「0 和 1 数量相等」「元音辅音数量相等」都走这条路。

「区间和为定值」再翻译成「两个前缀和之差为定值」，于是检查区间性质退化成比较两个标量。这是前缀和技巧的核心价值——把 $O(n)$ 的区间查询变成 $O(1)$ 的两点相减。

求「最长」就记首次出现的位置，求「个数」就记出现次数。这条对应关系要背熟：本题求最长，所以 first 只在键不存在时写入；而 560 题求子数组个数，哈希表存的是每个前缀和出现的次数且每次都要累加。搞混这一点会得到完全不同的错误。

预置「空前缀」条目是必需的，不是可选的。first[0] = -1 让以下标 0 开头的区间能够被配对。凡是用前缀和差值找区间的题，第一行代码就应该是这一句；忘记它的症状是「答案总是少了从头开始的那一段」。

端点开闭决定长度公式。这里配对位置 start 不属于答案区间，所以长度是 i - start 而非 i - start + 1，起点是 start + 1 而非 start。写之前先画一条数轴标清哪个端点被排除。

多解取最左就用严格大于。len > bestLen 而不是 >=，配合从左往右的扫描顺序，天然保证了同长度时保留最先出现的方案。

面试视角：这题的考点百分之百是「$\pm 1$ 映射 + 前缀和 + 哈希表存首次位置」这套组合拳。面试官通常会先让你说清「为什么滑动窗口在这里不行」——答「映射后元素有正有负，窗口收缩时区间和不单调，无法用双指针」；然后追问「哈希表里存的是什么、为什么只存第一次」；最后可能让你手推一遍 first[0] = -1 的必要性。能主动补一句「因为差值每步只变 ±1、范围在 $[-n, n]$，可以用数组代替哈希表把常数降下来」，是很自然的优化延伸。

易错点总结

错误写法：不预置 first.put(0, -1) → 用例 array = ["A","1"]，i = 1 时 diff 归零但表中无键 0，于是写入 first[0] = 1 并算出 len = 0，最终返回空数组；正确答案是整个数组。所有从下标 0 开头的合法区间都会被漏掉。

错误写法：每次都无条件 first.put(diff, i)（覆盖写入） → 用例 array = ["A","A","1","B","2"]，i = 2 时把 first[1] 从 0 改成 2，i = 4 时配对的起点变成 2、len = 2，最终返回 ["B","2"]；正确答案是长度 4 的 ["A","1","B","2"]。求最长必须与最早的同值位置配对。

错误写法：bestStart = start（忘记加一） → 用例 array = ["A","1"]，start = -1，bestStart 被设成 -1，截取时直接数组越界；即便 start 非负，也会把不属于答案的那个元素带进来。配对位置属于前缀，不属于区间。

错误写法：len = i - start + 1 → 用例 array = ["A","1"]，算出长度 3 而数组只有 2 个元素，截取越界。这里 start 是开端点，长度就是下标之差。

错误写法：更新条件写成 len >= bestLen → 用例 array = ["A","1","B","2"]，下标 0 到 1 与下标 2 到 3 都是长度 2 的合法区间（在更长答案出现之前），用 >= 会把 bestStart 更新到靠右的那个；题目要求返回最靠左的方案。

错误写法：用滑动窗口，右端点扩张、左端点在「不平衡」时收缩 → 用例 array = ["A","A","1","1"]，正确答案是整个数组；但窗口在 i = 1 时字母多出 2 个，若此时收缩左边界就会永久丢掉开头的 A，之后再也拼不出长度 4 的答案。映射后元素有正有负，约束不具单调性，滑动窗口不适用。

错误写法：哈希表存的是「差值出现的次数」而非「首次位置」 → 这是把 560 题的模板套错了。用例 array = ["A","1"]，次数信息无法还原出区间端点，根本算不出长度。求最长记位置、求个数记次数，两者不能混用。

错误写法：字母与数字的记号中途不一致（比如大写字母记 +1、小写字母记 -1） → 用例 array = ["A","a"]，两个都是字母本不构成合法区间，却被算成差值归零、返回长度 2；分类只有「字母」与「数字」两类，大小写属于同一类。

错误写法：用 array[i].equals("0") 这类逐个值比较来判定数字 → 用例 array = ["5"]，只判了 "0" 会把 "5" 误归为字母；应当用 Character.isDigit(ch) 或 ch >= '0' && ch <= '9' 做范围判定。

错误写法：bestLen 初值设成 -1 或 Integer.MIN_VALUE → 用例 array = ["A","A"]，不存在合法区间，末尾用负长度构造数组直接抛 NegativeArraySizeException；初值取 0 才能让「无解返回空数组」自然成立。

错误写法：Go 中返回 array[bestStart : bestStart+bestLen] 后调用方修改了原数组 → 返回的切片与入参共享底层数组，若判题或调用方随后改动 array，结果会跟着变；对返回值敏感的场景应显式 copy 一份。

相似题目

题目	难度	考察点
525. 连续数组	中等	与本题完全同构，把字母数字换成 1 和 0，可原样套用同一份代码
325. 和等于 k 的最长子数组长度	中等	目标和从 0 推广到任意 k，查表时要找 `diff - k` 而不是 `diff` 本身
560. 和为 K 的子数组	中等	求满足条件的子数组个数，哈希表要存出现次数并累加，而不是存首次位置
974. 和可被 K 整除的子数组	中等	前缀和先取模再按同余类配对，难点是负数取模必须归一化到非负
523. 连续的子数组和	中等	同为同余类配对，但额外要求子数组长度至少为 2，配对时要检查下标间隔
930. 和相同的二元子数组	中等	元素非负所以也能用「恰好 K = 至多 K 减至多 K-1」的双滑窗解，与本题形成对照
1074. 元素和为目标值的子矩阵数量	困难	把二维压成一维后对每对行边界跑一次本题的哈希配对，是模板的升维应用
LCR 011. 连续数组	中等	与 525 同题，可直接套用