LeetCode 面试题 17.18. 最短超串
目录
题目描述
题意分析
在数组
big中找一个最短的连续子数组，使它包含small中的所有元素。要返回的是这个子数组的左右端点下标，而不是长度也不是内容；若有多个同样短的答案，返回左端点最小的那个；若根本不存在这样的区间，返回空数组。
两个细节把题目框死了：一是「连续」，所以候选一定是区间而不是任意子集，这排除了排序、哈希去重之类会破坏顺序的做法；二是
small中元素互不相同，所以每个目标只需要在窗口里出现至少一次，不存在「需要两个 3」这种多重集需求，判定条件因此可以简化成计数命中的种类数。
最关键的算法信号是单调性：如果区间
[l, r]已经覆盖了全部目标，那么把右端点继续右移得到的[l, r']（r' > r）必然也覆盖——覆盖性对区间的扩张是单调的。这意味着对每个固定的右端点，存在唯一的「最靠右的合法左端点」，且这个左端点随右端点右移只增不减。有了这条，两个指针就都只需要单向走一遍，不必回退。
规模上
big可达十万量级，$O(n^2)$ 地枚举所有区间会超时，上面的单调性正好把它降到线性。
边界上要考虑：
big中可能根本不含某个目标元素，此时答案是空数组；big里可能有大量重复的目标元素，收缩时不能一见到目标就停；small长度可能为 1，此时答案是任意一个该元素所在的单点区间。
解法：滑动窗口维护有效区间
核心思路
暴力做法是枚举所有 $O(n^2)$ 个区间，对每个区间检查是否覆盖
small。即便用哈希把检查降到 $O(1)$ 摊销，枚举本身就已经超时了。瓶颈在于：左端点每次都从头重来，而前一个左端点已经得出的「覆盖到哪里才够」的信息被完全丢弃。
由前面的单调性观察可以重新组织搜索：固定右端点 r，我们只关心那个使
[l, r]恰好仍然合法的最大 l——比它更小的左端点只会让区间更长，不可能是答案；比它更大的左端点则已经不合法。而当 r 增加时，这个最优 l 绝不会变小（原来不合法的左端点，加入更多右侧元素后仍不合法与否只可能变好，但已经被更优解淘汰的位置不必回头）。于是 l 与 r 都只需单调右移，总移动次数被 $2n$ 限制住。
剩下的问题是如何 $O(1)$ 地判断「当前窗口是否覆盖全部目标」。这里维护两层结构构成不变量：
need记录每个目标元素的需求量（本题因元素互异恒为 1），window记录窗口内每个目标元素的实际出现次数，match记录「已经达到需求量的目标种类数」；任意时刻窗口合法当且仅当match == need.size()。match的存在把一次全表比对压成了一个整数比较，这是滑动窗口模板的核心。
match的更新必须严格踩在「跨过阈值的那一刻」：加入元素后计数恰好等于需求量时match++，移除元素后计数刚刚小于需求量时match--。用「恰好等于」和「刚刚小于」而不是「大于等于」和「小于等于」，是为了保证同一个目标不会被重复计数——窗口里有三个 1 时，match里 1 这个目标只能算一次。
解题步骤
- 先把
small装进need，每个元素的需求量置 1。题目已保证small内元素互不相同，所以不需要累加计数；needSize = need.size()就是要凑齐的目标种类数，这个值全程不变，先算好避免在循环里反复调用。- 右端点从左到右遍历
big，只有当元素在need中时才更新窗口。非目标元素对合法性毫无影响，把它们记进window只会浪费空间，还会让「窗口内目标种类数」这个语义变模糊。- 加入元素后立刻判断
cnt == need.get(val)决定是否match++。写成>=会让同一个目标的第二次、第三次出现都触发自增，match虚高，窗口尚未真正覆盖就被误判为合法。- 合法之后用
while而不是if持续收缩左端点。一次右移可能让窗口连续通过多个可收缩的位置（左边堆了一串非目标元素或重复目标），只收一次会留下大量冗余前缀，得到的区间不是最短的。- 在收缩循环的开头、移除元素之前更新答案。此刻的
[left, right]是合法的，长度可以参与竞争；一旦移除了左端元素，窗口可能已经不合法，再记录就是错的。用严格小于right - left + 1 < bestLen做比较，保证同长度时保留先出现的、也就是左端点更小的那个答案，正好符合题目要求。- 移除左端元素时同步递减计数，并在
cnt < need.get(drop)时match--。这是加入操作的精确逆运算；漏掉这一步，match会永远停在满值，左指针一路滑到底，答案退化成一个不合法的短区间。- 循环结束后用
bestL == -1判断是否找到过合法窗口。用哨兵而不是「bestLen是否还是初值」来判断更直观，也避免了长度比较里的溢出隐患。
以
big = [1, 2, 3, 2, 1, 4, 5]、small = [1, 4]走一遍。need = {1:1, 4:1}，needSize = 2，window = {}，match = 0，left = 0，bestLen = +∞。
right = 0，值 1，是目标，
window = {1:1}，计数恰好等于需求，match = 1。不合法，不收缩。
right = 1，值 2，不是目标，跳过。right = 2，值 3，跳过。right = 3，值 2，跳过。
right = 4，值 1，是目标，
window = {1:2}，计数 2 不等于需求 1，match仍为 1。不合法。这里正是「用==而非>=」发挥作用的地方：目标 1 已经算过一次，不能再算。
right = 5，值 4，是目标，
window = {1:2, 4:1}，计数恰好等于需求，match = 2，窗口合法，进入收缩循环。
收缩第 1 轮：
[0, 5]长度 6 < ∞，记bestL = 0、bestR = 5、bestLen = 6。移除big[0] = 1，window[1]降为 1，仍不小于需求 1，match保持 2，left = 1。
收缩第 2 轮：
[1, 5]长度 5 < 6，更新bestL = 1、bestR = 5、bestLen = 5。移除big[1] = 2，非目标，left = 2。
收缩第 3 轮：
[2, 5]长度 4，更新为bestL = 2、bestR = 5。移除big[2] = 3，非目标，left = 3。
收缩第 4 轮：
[3, 5]长度 3，更新为bestL = 3、bestR = 5。移除big[3] = 2，非目标，left = 4。
收缩第 5 轮：
[4, 5]长度 2，更新为bestL = 4、bestR = 5、bestLen = 2。移除big[4] = 1，window[1]降为 0，小于需求 1，match减到 1，left = 5，循环退出。
right = 6，值 5，不是目标，跳过。遍历结束。
bestL = 4不等于 -1，返回 [4, 5]。手工核对：big[4..5] = [1, 4]恰好包含目标 1 和 4，长度 2；数组里 1 出现在下标 0 和 4，4 只出现在下标 5，任何合法区间都必须含下标 5，配上最近的 1 就是下标 4，长度 2 已是下界，答案正确。
代码实现
// 用哈希表统计窗口内每个目标元素出现次数，并维护已满足的目标数 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 为
big的长度、m 为small的长度。凭什么？建need是 $O(m)$；主循环里右指针恰好走 n 步，左指针全程只增不减、最多也走 n 步，两者合计 $2n$ 次移动，每次移动只做常数次哈希读写。虽然内层是while，但它不会让任何一个下标被左指针访问两次，所以整体仍是线性。- 空间复杂度：$O(m)$。凭什么？
need恰好存small的 m 个元素；window只登记出现过的目标元素，键集是need的子集，同样不超过 m；其余是常数个下标与计数变量。与big的长度无关，即使big有十万个不同的非目标元素，也不会进入任何哈希表。
关键点总结
- 覆盖性的单调性是滑动窗口成立的前提：只有当「区间变长不会让合法变不合法」时，左右指针才能都只走一遍。遇到新题先验证这条，若某个约束在扩张时可能被破坏（例如同时要求「不含某元素」和「含某元素」），窗口法就要改造甚至换算法。
- 用一个整数
match代替整表比对：把「所有目标都满足」这个 $O(m)$ 的判断压缩成一次比较，是模板从 $O(nm)$ 降到 $O(n)$ 的真正原因。关键在于match只在跨过阈值的瞬间加减，而不是每次改动都重算。- 加入与移除必须是严格互逆的一对操作：加入时用
cnt == need，移除时就必须用cnt < need；两边的判据不对称，match就会漂移。写完模板后用「加一个再删一个应回到原状态」自检一遍是很有效的验证手段。- 答案在窗口合法时记录，而不是在收缩之后：这决定了
if更新语句必须写在移除操作之前。顺序错了不会报错，只会静默返回一个偏移一位的区间。- 「多解取左端点最小」靠严格小于自然实现：比较时用
<而非<=，先出现的同长度答案就不会被后来者覆盖。凡是题目对多解有额外偏好的，都要检查一遍比较符的严格性。- 面试视角：这题是 76 最小覆盖子串的数组版，代码几乎可以照搬，考的是模板的熟练度与边界处理。答完后主动补两句会加分——一是「因为
small元素互异，need其实可以退化成Set，window里的计数仍要保留因为big中会重复」，二是「若small允许重复，需求量就要累加，其余代码一行不用改」，这说明你理解的是模板的语义而不是形状。
易错点总结
- 错误写法：加入元素后用
cnt >= need.get(val)判断是否match++。用例big = [1, 1, 4], small = [1, 4]→ 下标 1 的第二个 1 也会触发自增，match变成 2，窗口[0, 1]被误判为合法并记为答案[1, 1]；正确答案是[1, 2]。必须用==只在恰好达标那一刻计数。- 错误写法：收缩用
if而不是while。用例big = [1, 2, 3, 2, 1, 4, 5], small = [1, 4]→ 右端点走到 5 时先记下[0, 5]长度 6，然后只收缩一次就退出，后续再也没能把长度压下去，最终返回[0, 5]；正确答案是[4, 5]长度 2。一次扩张可能允许连续多次收缩。- 错误写法：把更新答案的语句写在移除左端元素之后。同样用例
big = [1, 2, 3, 2, 1, 4, 5], small = [1, 4]→ 最后一轮先把下标 4 的 1 移出、left变成 5，再记录[5, 5]长度 1；这个区间只含元素 4，根本不覆盖目标 1。必须在窗口仍合法时抢先记录。- 错误写法：移除元素时忘记
match--。用例big = [1, 4, 9, 9, 9], small = [1, 4]→match一旦到 2 就再也降不下来，左指针在收缩循环里一路滑到left > right才停，途中把[1, 1]这个只含元素 4 的单点区间当成更短的答案记了下来，最终返回[1, 1]；正确答案是[0, 1]。加入与移除必须成对更新。- 错误写法：移除时的判据写成
cnt <= need.get(drop)。用例big = [1, 1, 4], small = [1, 4]→ 窗口{1:2, 4:1}移除一个 1 后计数降为 1，1 <= 1成立触发match--，窗口被误判为不合法而提前停止收缩，返回[0, 2]；正确答案是[1, 2]。只有掉到需求量以下才算失去一个目标。- 错误写法：长度比较用
<=而不是<。用例big = [1, 4, 9, 1, 4], small = [1, 4]→ 两个长度均为 2 的合法区间[0, 1]与[3, 4]中，后者会覆盖前者返回[3, 4]；题目要求多解时取左端点最小，正确答案是[0, 1]。- 错误写法：把非目标元素也记进
window。用例big含十万个互不相同的非目标数 →window膨胀到 $O(n)$，空间从 $O(m)$ 退化成 $O(n)$；更糟的是若同时把match的判定改成比较window.size() == needSize，第一个非目标元素就会让判定永远失真，返回任意错误区间。- 错误写法：不存在合法窗口时返回
new int[]{-1, -1}或null。用例big = [1, 2, 3], small = [4]→ 4 从未出现，match始终为 0，若返回[-1, -1]会被判错，返回null则可能在判题侧抛异常；题目明确要求返回空数组。- 错误写法：
bestLen初值设成big.length而不是极大值。用例big = [1, 4], small = [1, 4]→ 唯一的合法区间长度恰好等于 2，2 < 2不成立，答案永远不被记录，最终返回空数组；正确答案是[0, 1]。初值必须严格大于任何可能的合法长度。- 错误写法：Go 里用
if window[val] > 0判断元素是否是目标。用例big = [9, 1, 4], small = [1, 4]→map的零值读取不会报错但也不区分「不存在」与「存在且为 0」，把非目标的 9 误判后window被污染，match的语义随之失效。判断是否为目标必须查need并用_, ok :=的两值形式。- 错误写法：左指针的循环条件漏掉
left <= right。用例small为空数组时needSize = 0，match == needSize从一开始就成立 → 左指针会在右指针还停在 0 时越过它，right - left + 1变成 0 甚至负数，记录出非法区间。加上边界条件可以让窗口永远保持非空。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 76. 最小覆盖子串 | 困难 | 目标串允许重复字符，需求量要累加而非恒为 1，且返回的是子串内容不是下标 |
| 567. 字符串的排列 | 中等 | 窗口长度固定，收缩退化为定长右移，且要求「恰好相等」而非「至少覆盖」 |
| 438. 找到字符串中所有字母异位词 | 中等 | 定长窗口且要收集全部起点，答案是列表而非单个最优解 |
| 209. 长度最小的子数组 | 中等 | 合法性由数值和的阈值决定，靠一个累加变量即可，完全不需要哈希表 |
| 632. 最小区间 | 困难 | 覆盖对象是 k 个有序列表各出一个数，窗口开在归并后的序列上并按值域而非下标度量 |
| 30. 串联所有单词的子串 | 困难 | 元素是等长单词，需按单词长度分组做多条独立窗口，命中后还要整词回退 |