LeetCode 面试题 17.18. 最短超串

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

题目描述

✅ 面试题 17.18. 最短超串

image-20260928231525740

题意分析

在 big 中找到包含 small 全部元素的最短连续子数组，目标元素在窗口中的先后顺序不受限制。small 非空且元素互不相同，每种只需至少出现一次；返回包含两端的下标 [left, right]，等长时选左端点更小的区间，无解返回空数组。

解法：滑动窗口维护有效区间

核心思路

[!blue]

固定左端点时，向右扩展窗口只会增加元素，已经满足的覆盖需求不会丢失；固定右端点时，向右移动左端点会让窗口更短，直到某种目标缺失。这种单调变化适合用两个只向前移动的指针维护窗口 [left, right]。

need 记录目标元素及需求次数一，window 只统计这些目标在当前窗口中的次数。match 表示已经满足的目标种类数，不是目标元素的总出现次数：某种目标从零次变成一次时，match 才加一，多出的副本不会继续增加它。于是 match == need.size() 等价于窗口覆盖完整。

右端每加入一个元素就更新对应计数。窗口一旦完整，先记录当前区间，再移除左端元素并推进 left；如果移除的是非目标，或这个目标仍有副本，窗口依然完整，可以继续缩短。只有某种目标次数从一变为零时，match 才减一，此时停止收缩，等待右端再次补足它。

左端移走后不需要回退：每个被移走的左端点，都已经在当前右端点下形成过合法区间并被记录。未来用同一个左端点，只会得到更长的区间，不可能改进最短答案。对仍保留的左端点，右端继续扩展直到首次可行，再尽量收缩，所以不会漏掉更短解。

最佳答案只在长度严格缩短时更新。右端按递增顺序处理，等长窗口的左端也随右端递增，先遇到的就是起点更早的那个；不在等长时覆盖，便满足题目的并列要求。若始终没有完整窗口，bestL 保持为负，返回空数组。

解题步骤

  1. 为 small 中的每个目标建立需求一，初始化空窗口、match = 0 和未找到答案的标记。
  2. 右端逐项扩展，只对目标元素更新频次，并在首次达标时增加 match。
  3. 只要窗口完整，先比较区间长度，再移除左端元素，必要时减少 match。
  4. 覆盖缺失后停止收缩，继续扩展右端；最终返回记录的两端下标或空数组。

代码实现

// 用哈希表统计窗口内每个目标元素出现次数，并维护已满足的目标数 match。
class Solution {
    public int[] shortestSeq(int[] big, int[] small) {
        Map<Integer, Integer> need = new HashMap<>();

        for (int num : small) {
            need.put(num, 1);
        }

        Map<Integer, Integer> window = new HashMap<>();
        int match = 0;
        int needSize = need.size();

        int left = 0;
        int bestL = -1;
        int bestR = -1;
        int bestLen = Integer.MAX_VALUE;

        for (int right = 0; right < big.length; right++) {
            int val = big[right];

            if (need.containsKey(val)) {
                int cnt = window.getOrDefault(val, 0) + 1;

                window.put(val, cnt);

                // 频次第一次达到要求才增加达标种类，多余副本不重复计数。
                if (cnt == need.get(val)) {
                    match++;
                }
            }

            while (match == needSize && left <= right) {
                // 移出左端前先记录合法窗口，只在严格缩短时覆盖答案。
                if (right - left + 1 < bestLen) {
                    bestLen = right - left + 1;
                    bestL = left;
                    bestR = right;
                }

                int drop = big[left];

                if (need.containsKey(drop)) {
                    int cnt = window.get(drop) - 1;

                    window.put(drop, cnt);

                    // 移出后仍有足够副本时，这类目标依然达标。
                    if (cnt < need.get(drop)) {
                        match--;
                    }
                }

                left++;
            }
        }

        if (bestL == -1) {
            return new int[0];
        }

        return new int[] {
            bestL,
            bestR,
        };
    }
}

// 用哈希表统计窗口内每个目标元素出现次数，并维护已满足的目标数 match。
func shortestSeq(big []int, small []int) []int {
    need := map[int]int{}
    for _, num := range small {
        need[num] = 1
    }

    window := map[int]int{}
    match := 0
    needSize := len(need)

    left := 0
    bestL := -1
    bestR := -1
    bestLen := int(^uint(0) >> 1)

    for right, val := range big {
        if _, ok := need[val]; ok {
            window[val]++
            // 频次第一次达到要求才增加达标种类，多余副本不重复计数。
            if window[val] == need[val] {
                match++
            }
        }

        for match == needSize && left <= right {
            // 移出左端前先记录合法窗口，只在严格缩短时覆盖答案。
            if right-left+1 < bestLen {
                bestLen = right - left + 1
                bestL = left
                bestR = right
            }

            drop := big[left]
            if _, ok := need[drop]; ok {
                window[drop]--
                // 移出后仍有足够副本时，这类目标依然达标。
                if window[drop] < need[drop] {
                    match--
                }
            }
            left++
        }
    }

    if bestL == -1 {
        return []int{}
    }

    return []int{
        bestL,
        bestR,
    }
}

复杂度分析

  • 时间复杂度：期望 $O(n+m)$，其中 n、m 分别为 big、small 的长度。建表处理 m 个元素，两个指针各最多经过 big 一次，哈希操作期望为常数时间。
  • 空间复杂度：$O(m)$，需求表和窗口表只保存目标元素。

关键点总结

[!green]

  • match 按目标种类是否达标变化，多余副本不重复计数。
  • 完整时收缩，不完整时扩展；移走的左端点无需重新考虑。
  • 长度使用 right - left + 1，只在严格缩短时覆盖答案。

易错点总结

[!yellow]

  • 每加入或移出一个目标都修改 match，会把多余副本误当作新的满足或新的缺失。
  • 必须在移除左端前记录当前合法窗口，移除后它可能已经不再完整。
  • 只收缩一次就扩展右端，可能保留不必要的前缀，漏掉当前能取得的更短区间。
  • 用小于等于更新最佳长度，会覆盖起点更早的等长结果。

相似题目

题目 难度 关联与区别
76. 最小覆盖子串 困难 同样寻找最短覆盖区间，本题small元素互异，只需每种出现一次；原题目标字符串可能含重复需求。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/38501628
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！