一. 定义

  • 滑动窗口是一种基于双指针的一种思想，两个指针指向的元素之间形成一个窗口。滑动窗口通过维护一个窗口不断滑动，来更新答案。
  • 滑动：说明这个窗口是移动的，也就是移动是按照一定方向来的。
  • 窗口：窗口大小并不是固定的，可以不断扩容直到满足一定的条件；也可以不断缩小，直到找到一个满足条件的最小窗口；当然也可以是固定大小。
  • 需要注意的细节：
    1. 那么如何向窗口中添加新元素
    2. 如何缩小窗口
    3. 在窗口滑动的哪个阶段更新结果

  • 滑动窗口算法可以用以解决数组/字符串的子元素问题，它可以将嵌套的循环问题，转换为单循环问题，降低时间复杂度。

    二. 模板

    1. 理论
    窗口实际是两个指针之间形成的区域。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动：

    1. 初始化窗口：在**序列(字符串/数组)**中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right]称为一个窗口。
    2. 寻找可行解：先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求。
    3. 优化可行解：停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求。同时，每次增加 left，我们都要更新一轮结果。
    4. 找到最优解：重复第 2 和第 3 步，直到 right 到达序列的尽头。

2. 模板代码

  1. // 情况一：寻找最长的
  2. 初始化left，right，result，bestResult
  3. while (右指针没有到结尾) {
  4.   窗口扩大，加入right对应元素，更新当前result
  5.   while (result不满足要求) {
  6.     窗口缩小，移除left对应元素，left右移
  7.   }
  8.   更新最优结果bestResult
  9.   right++;
  10. }
  11. 返回bestResult
  13. // 情况二：寻找最短的
  14. 初始化left，right，result，bestResult
  15. while (右指针没有到结尾) {
  16.   窗口扩大，加入right对应元素，更新当前result
  17.   while (result不满足要求) {
  18.     更新最优结果bestResult
  19.     窗口缩小，移除left对应元素，left右移
  20.   }
  21.   right++;
  22. }
  23. 返回bestResult

三. 经典题目

1. 最大滑窗

2. 最小滑窗