最小覆盖子串(LC76,滑动窗口)
哪些公司问过
答案要点
- 用滑动窗口加双指针,右扩左缩,达到 O(N) 时间、O(M) 空间
- 哈希表/计数数组记录每种所需元素的个数,维护窗口内计数
- 右指针扩展纳入元素,某种数量达需求时已覆盖种类数加一
- 已覆盖种类数等于总需求时收缩左边界,保持覆盖下更新最短长度
- 收缩判断条件是「窗口已覆盖所有所需种类」,重复元素需计数够才算满足
易错点
- 只统计种类不看每种数量,重复元素场景会误判覆盖
- 收缩时忘记同步更新计数和已满足种类数,导致判断错误
- 更新最短长度的时机放错,应在窗口满足覆盖时更新
- 目标集合为空或源串过短等边界未处理
面试官常见追问
- 为什么时间是 O(N) 而不是 O(N^2)?
- 怎么判断窗口「恰好覆盖」而不漏算重复元素?
- 如果要的是恰好包含而非至少包含,解法要改吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 数组和链表的区别与适用场景173 场
- 经典算法题:最长回文子串、无重复最长子串、最大子数组和141 场
- 合并有序数组与合并区间66 场
- 三数之和:排序加双指针50 场
- 字符串相加(大数加法)20 场
- 字符串匹配:KMP 算法18 场
- 字符串反转的实现与注意事项17 场
- 接雨水问题的三种解法14 场
- 螺旋矩阵遍历14 场
- 两数之和的几种解法12 场