面试官爱考滑动窗口——能把O(n²)暴力降到O(n)。能识别场景是关键。
场景:问连续子数组/子串满足某条件的"最长/最短/最优",且条件关于窗口扩/缩单调。
定长(k):r前进,窗口>k就l前进。维护聚合。
变长:r无条件前进;窗口非法就l前进。合法窗口时更新答案。
聚合增量维护——字符计数map、和、单调队列里的max——每步O(1)均摊。
经典题:最长不重复子串、最小覆盖子串、定长最大和、至多k种字符的最长子串。
看到"最长/最短/最优连续X满足..."且窗口单调扩缩改变合法性时,我就用滑动窗口。模板:双指针l、r。定长:每步r++,r-l+1>k就l++。变长:r无条件++,while(非法)l++。"最长不重复子串":字符计数map,r++计数加,任何计数>1就l++减。窗口合法时更新答案。"最小覆盖子串":记还缺多少必需字符,missing==0时缩左。关键是"合法"要是单调谓词——如果不单调,滑动窗口不成立,多半要DP或hash+计数。
"不同字符"类约束配HashMap/计数器。
单调队列做"窗口内最大"O(1)均摊——leetcode 239。
即答侠把定长/变长两模板并排放,配6道例题——模式识别自动化。
滑动窗口是双指针的一种——两个指针都只前进。双指针还包括相向而行(有序数组求和)。
经典滑动窗口里几乎不会——真要就多半得换DP或别的结构。