编程算法面试题

滑动窗口:定长和变长模板

什么场景用滑动窗口?给出模板。

为什么面试官会问这道题

面试官爱考滑动窗口——能把O(n²)暴力降到O(n)。能识别场景是关键。

如何回答

  1. 1

    场景:问连续子数组/子串满足某条件的"最长/最短/最优",且条件关于窗口扩/缩单调。

  2. 2

    定长(k):r前进,窗口>k就l前进。维护聚合。

  3. 3

    变长:r无条件前进;窗口非法就l前进。合法窗口时更新答案。

  4. 4

    聚合增量维护——字符计数map、和、单调队列里的max——每步O(1)均摊。

  5. 5

    经典题:最长不重复子串、最小覆盖子串、定长最大和、至多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或别的结构。

面试时担心忘词?即答侠实时助你

即答侠 AI 实时监听面试对话,自动识别问题并即时生成回答建议——无感辅助,让你从容应对每一道题。

免费试用即答侠