面试题库 › C++ / 后端 › 最短超串:包含全部目标元素的最短子数组

最短超串:包含全部目标元素的最短子数组

难度 ★★☆在 2 场真实面经中被问到 方向:C++ / 后端考点:数组与字符串

哪些公司问过

华为2

常见岗位:C/C++ 软件开发

答案要点

  1. 滑动窗口 + 哈希表,统计窗口内目标元素出现次数和已覆盖种类数
  2. 右指针扩张,覆盖种类等于目标数时开始收缩左指针
  3. 收缩时先更新答案,只在长度严格更短时更新,保证左端点最小
  4. 目标元素计数降到 0 时覆盖种类减一,窗口失效停止收缩
  5. 每个元素最多进出窗口一次,时间 O(n),空间 O(m)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题