Skip to content

WXG. SHIT. 1 最小覆盖子串

核心思想 :先扩张,再收缩

算法通过维护一个左右边界不断变化的“窗口”来寻找答案:

  • 扩张阶段(寻找可行解): 移动右指针以扩大窗口,直到窗口内包含了字符串 t 中的所有字符(包括重复字符)。
  • 收缩阶段(寻找最优解): 一旦窗口有效(即包含了所有要求的字符),就开始移动左指针来收缩窗口。在保持窗口有效的前提下,尽可能去掉多余的字符,从而找到当前最小的有效子串
  • 收缩时候,need[s[l]]==window[s[l]] 要做这个条件检查,一旦满足就说明此时刚好达到要求,停止左指针收缩,转向 r 扩张。