---

[!info] related notes 算法面试题型 MOC

滑动窗口

分享丨【算法题单】滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环） - 讨论 - 力扣（LeetCode）

定长滑动窗口

题单

• 定长子串中元音的最大数目
• 可获得的最大点数

不定长滑动窗口

不定长滑动窗口主要分为三类：求最长子数组，求最短子数组，求子数组个数。

注：滑动窗口相当于在维护一个队列。右指针的移动可以视作入队，左指针的移动可以视作出队。

题单

• 将x减到0的最小操作数

信息参考

作者：灵茶山艾府 链接：https://leetcode.cn/discuss/post/0viNMK/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Overview

滑动窗口的英文名非常直白，就叫 Sliding Window。它是**双指针（Two Pointers）**技巧中非常经典且特殊的一种应用分支。

如果要把滑动窗口的本质掰开揉碎了讲，我们可以从“它解决了什么问题”以及“它的核心运作机制”两个方面来看。

1. 为什么要有滑动窗口？（它解决了什么问题）

滑动窗口诞生的最大意义就是降维打击，用空间换时间（或者说用指针状态换取重复计算），将嵌套循环转化为单循环。

假设没有滑动窗口，面对上一题“寻找满足条件的连续子数组”，人类直觉的暴力解法是：

• 选定索引 0 作为起点，往后加，看加到哪里满足条件。
• 选定索引 1 作为起点，往后加，看加到哪里满足条件。
• ……以此类推。

这种解法需要两层 for 循环，时间复杂度是 $O(N^2)$。当数组长度达到 $10^5$ 时（像上一题的提示那样），$O(N^2)$ 会执行 100 亿次操作，必定会“超出时间限制”。

滑动窗口的本质，就是避免让左端点每次都“从头再来”。 当右端点探索到了某个位置，发现窗口内的值已经足够了，那么左端点只需要顺势向前滑动，剔除掉最左边的元素即可，完全不需要退回到起点重新计算。这样，左右指针在整个过程中都只进不退，每个元素最多进窗口一次、出窗口一次，时间复杂度就被完美压缩到了 $O(N)$。

2. 滑动窗口的核心机制（毛毛虫爬行法）

你可以把滑动窗口想象成一只在树叶上吃东西的毛毛虫，或者是一个弹簧。它永远包含四个标准动作，这四个动作构成了滑动窗口的“万能心法”：

1. 进（Expand）： 毛毛虫的头（右指针 right）一直努力向前伸，把新的元素吞进窗口里。在这个阶段，窗口是不断扩大的。

2. 判（Condition）： 每次吞进新元素后，都要判断一下毛毛虫的胃口：当前肚子里的东西（窗口内的状态，比如 sum）是否满足了题目的条件？或者是否撑破了肚皮（违背了限制）？

3. 出（Shrink）： * 找最短/最少（如上一题）： 一旦满足了条件，毛毛虫的尾巴（左指针 left）就开始往前缩，把吃进去的旧东西排出来，试图让身体变得尽量短，直到刚好不满足条件为止。

   • 找最长/最多： 一旦违背了限制，尾巴（左指针 left）就必须往前缩，吐出旧东西，直到身体重新恢复到合法的状态。

4. 算（Update）： 在“进”和“出”的过程中，在合适的时机记录下毛毛虫身体的长度（更新 ans 结果）。

3. 如何一眼看穿这道题该用滑动窗口？

只要在题目描述中同时看到以下几个关键字，你就可以条件反射地想到 Sliding Window：

• 连续（Continuous / Subarray / Substring）：比如连续子数组、子串。（这是最核心的前提，如果不连续，只能用动态规划或回溯）。
• 最值：求最长（Longest）、最短（Shortest）、最大（Maximum）。
• 单调性：数组里的元素通常是正数，保证了窗口扩大的时候状态是单调增加的，窗口缩小的时候状态是单调递减的（这样左右指针才不会出现需要“后退”的情况）。