Skip to content
363045841 的博客
Main Navigation
首页
项目
Appearance
Menu
Return to top
文章
WXG. SHIT. 1 最小覆盖子串
核心思想 :先扩张,再收缩
算法通过维护一个左右边界不断变化的“窗口”来寻找答案:
扩张阶段(寻找可行解):
移动
右指针
以扩大窗口,直到窗口内包含了字符串 t 中的所有字符(包括重复字符)。
收缩阶段(寻找最优解):
一旦窗口有效(即包含了所有要求的字符),就开始移动
左指针
来收缩窗口。在保持窗口有效的前提下,尽可能去掉多余的字符,从而找到当前最小的有效子串
收缩时候,
need[s[l]]==window[s[l]]
要做这个条件检查,一旦满足就说明此时刚好达到要求,停止左指针收缩,转向
r
扩张。