LeetCode 面试题 17.05. 字母与数字

约 5 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 程序员面试金典（第 6 版） 字节
标签
数组 哈希表 前缀和

题目描述

✅ 面试题 17.05. 字母与数字

image-20260928223202822

题意分析

在数组中找一段连续子数组，使字母元素与数字元素的个数相等，并返回最长的一段。具体是哪个字母、数字大小是多少都不影响计数；长度相同时，要求返回左端点最早的片段。若没有符合条件的非空片段，返回空数组。

解法：前缀差值 + 哈希表

核心思路

[!blue]

把字母元素看作 $+1$、数字元素看作 $-1$，一段中两类数量相等，就等价于这段的和为 $0$。用 diff 记录从数组开头到当前位置的“字母数减数字数”，不必真正改写输入数组。

设下标 j 和 i 处的前缀差值相同，则从 j + 1 到 i 的差值等于两个前缀相减，结果为 $0$。因此扫描到 i 时，只需查找之前是否出现过当前 diff，就能定位一个以 i 为右端的平衡片段，其长度为 i - j。

用哈希表 first 保存每个差值第一次出现的下标。对于固定右端 i，差值相同的位置越早，片段越长；较晚的位置不可能给出更优长度，所以首次位置一旦记录就不覆盖。这样每个右端只需一次查表，而不必重新枚举所有左端。

数组开始前的空前缀差值为 $0$，把它记在下标 $-1$：first[0] = -1。当当前前缀本身已经平衡时，就能得到区间 [0, i]，长度也统一写成 i - (-1)。

最佳答案只在候选长度严格大于 bestLen 时更新。因为右端 i 从小到大扫描，对于同样的长度，越早遇到的右端对应的左端也越早；等长时保留原答案，就满足最小左端要求。代码在差值首次出现时先登记当前位置，此时算出的长度为 $0$，不会误更新答案。

最后按 bestStart 和 bestLen 截取结果。若输入为空或没有平衡片段，bestLen 保持 $0$，自然返回空数组。

解题步骤

  1. 初始化 first[0] = -1、diff = 0，最佳长度与起点都设为 $0$。
  2. 扫描到下标 i 时，字母令 diff++，数字令 diff--。
  3. 若 diff 尚未登记，保存下标 i；否则保留其原有首次位置。
  4. 令 j = first[diff]，候选长度为 i - j；仅当长度更大时，更新 bestStart = j + 1 和 bestLen。
  5. 返回从 bestStart 开始、长度为 bestLen 的连续片段。

代码实现

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)$，哈希表操作按平均常数时间计。
  • 空间复杂度：$O(n)$，前缀和首次位置记录。 Java 复制返回片段，Go 返回原数组的切片视图。

关键点总结

[!green]

  • 相同前缀差值之间的区间贡献为零，正好表示两类元素等量。
  • 保存最早前缀位置解决“最长”，按右端递增且仅严格增长时更新解决“左端最早”。
  • 空前缀放在 $-1$，使从首项开始的区间也遵循相同长度公式。

易错点总结

[!yellow]

  • 每次覆盖首次位置会缩短候选区间。
  • 长度相等也覆盖答案，可能失去最早起点。
  • 统计整段数组总数而不定位区间，不能得到最长连续片段。

相似题目

题目 难度 关联与区别
525. 连续数组 中等 把字母与数字元素映成正负1，等量区间等价于和为0，最长长度由最早前缀位置确定。
560. 和为 K 的子数组 中等 同样按前缀和相等定位零和区间，本题保存最早位置求最长，而非保存频次计数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/60114818
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！