概述

简介

滑动窗口算法是一种处理字符串或数组问题的技术，它可以用一个固定大小的窗口在输入数据上滑动，从而优化时间复杂度。

算法流程

滑动窗口算法的基本思想是维护一个窗口的起始和结束位置，根据题目要求不断地调整窗口的大小和位置，同时更新窗口内的信息，如最大值、最小值、平均值、异位词等。

从类型上说主要有：

• 固定窗口大小
• 窗口大小不固定，求解最大的满足条件的窗口
• 窗口大小不固定，求解最小的满足条件的窗口

固定窗口大小

对于固定窗口，我们只需要固定初始化左右指针 l 和 r，分别表示的窗口的左右顶点，并且保证：

1. l 初始化为 0
2. 初始化 r，使得 r - l + 1 等于窗口大小
3. 同时移动 l 和 r
4. 判断窗口内的连续元素是否满足题目限定的条件
   1. 如果满足，再判断是否需要更新最优解，如果需要则更新最优解
   2. 如果不满足，则继续。

可变窗口大小

对于可变窗口，我们同样固定初始化左右指针 l 和 r，分别表示的窗口的左右顶点。后面有所不同，我们需要保证：

1. l 和 r 都初始化为 0
2. r 指针移动一步
3. 判断窗口内的连续元素是否满足题目限定的条件
   1. 如果满足，再判断是否需要更新最优解，如果需要则更新最优解。并尝试通过移动 l 指针缩小窗口大小。循环执行
   2. 如果不满足，则继续。

形象地来看的话，就是 r 指针不停向右移动，l 指针仅仅在窗口满足条件之后才会移动，起到窗口收缩的效果。

img

应用场景

滑动窗口算法可以解决一些常见的子串或子数组问题，例如最长无重复子串、最小覆盖子串、最大和子数组等。

模版代码

初始化慢指针 = 0
初始化 ans
for 快指针 in 可迭代集合
   更新窗口内信息
   while 窗口内不符合题意
      扩展或者收缩窗口
      慢指针移动
   更新答案
返回 ans