滑动窗口

滑动窗口用途

• 用于解决连续子串、连续子数组问题

---

模式说明

• 用两个指针,标识窗口边界
• 用一些状态变量标识窗口当前状态
• 窗口长度可以固定,也可以可变，取决于具体问题
• 窗口有左边扩大缩小,右边扩大缩小，和整体左右移动几种移动形式

---

一般步骤

1. 判断是整体移动类型,还是左右移动类型
2. 如何表示当前窗口状态(如：窗口长度,最大一般设为0，最小一般设为超过总长度的值)
3. 有多少种临界状态,临界状态如何移动窗口

---

力扣题目举例

---

• 3. 无重复字符的最长子串:给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

  步骤一: 判断是整体移动类型,还是左右移动类型

  • 很明显该题目不是固定长度的，所以选择 左右移动类型。

  步骤二：如何表示当前窗口状态

  • 窗口中子串是否重复的状态,这里使用map,不使用字符串的index等方法
  • 窗口中子串长度

  步骤三：有多少种临界状态,临界状态如何移动窗口

  • 当窗口没有重复字符,右边窗口向右扩展
  • 当窗口有重复字符,左边窗口向右扩展

  编码：

   def 无重复字符的最长子串(目标字符串):
     # 边界情况 略
     # 定义 左右移动类型 窗口指针
     窗口左边下标=0
     窗口右边下标=0
     # 定义窗口状态变量
     当前存在字符字典=Map()
     当前窗口长度=0
     # 循环判断窗口状态,并且做出相应处理
     最大长度=0
     for 一个字符 in 目标字符串: 
       if  当前存在字符字典[一个字符]==None:
         # 右边窗口右移动
         窗口右边下标+=1
         # 加入字典
         当前存在字符字典[一个字符]=True
         # 长度加1
         当前窗口长度+=1
         最大长度=当前窗口长度
       else:
         # 左边窗口右移动
         窗口左边下标+=1
         # 移除字典
         当前存在字符字典[一个字符]=None
         # 长度减1
         当前窗口长度-=1
     return 最大长度
  

---

• 30. 串联所有单词的子串：给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

  注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。
  步骤一: 判断是整体移动类型,还是左右移动类型
  1. 该提意可知,整体移动类型(长度为words 中的单词)

  步骤二：如何表示当前窗口状态
  1. 所有words的中长度
  2. 一个word的长度
  3. 当前word的所有单词，及单词重复出现的次数:Map
  步骤三：有多少种临界状态,临界状态如何移动窗口
  1. 从0移动到目标字符串长度-所有words的中长度的范围,判断移动到index时,index到所有words的中长度 的字符是否满足,当前word的所有单词的Map
  2. 不满足则整体移动窗口,调整index的位置,知道满足为止
  编码：

---

• 76. 最小覆盖子串

---

• 209. 长度最小的子数组

---

• 239. 滑动窗口最大值

---

• 567. 字符串的排列

---

• 632. 最小区间