滑动窗口用途
- 用于解决连续子串、连续子数组问题
模式说明
- 用两个指针,标识窗口边界
- 用一些状态变量标识窗口当前状态
- 窗口长度可以固定,也可以可变，取决于具体问题
-
窗口有左边扩大缩小,右边扩大缩小，和整体左右移动几种移动形式
一般步骤
- 判断是整体移动类型,还是左右移动类型
- 如何表示当前窗口状态(如：窗口长度,最大一般设为0，最小一般设为超过总长度的值)
- 有多少种临界状态,临界状态如何移动窗口
力扣题目举例
-
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的位置,知道满足为止
编码：
