一、滑动窗口是什么
滑动窗口是双指针套路的一种，一般用于求解满足要求的子串或一段连续数组
在数据或字符串中定义两个指针，left和right，一前一后，求解在left到right这一段数据内满足题意的数据。
二、套路模板
借用labuladong的模板可以解决大部分滑动窗口的题目，基本模板如下
def slidingWindow(s, t):
need = {} # 满足条件的窗口
window = {} # 窗口计数器
# need 和 window 一般是用字典表示，有时候也可能会用列表或者其他数据结构表示，具体的应该根据题目变化，有的题目可能就不需要这两个变量。
for i in t: # 初始化模板数据
need[i] = need.get(i, 0) + 1 # need.get(i, 0) 字典操作，往need里面添加数据，如果i不在need里面则初始化赋值为0
l = 0 # 左指针
r = 0 # 右指针
vaild = 0 # 满足条件的计数器
# 可能还需要定义用于返回答案或者其他临时的变量，具体需要根据题目需求定义
while r < len(s): #固定右指针遍历
c = s[r] # 移入窗口的字符
# 接下来是更新数据
# ...
# 判断是否需要收缩窗口，即左指针是否需要移动,这一步是关键，不同场景判断条件不一样
while (...):
d = s[l]
l += 1
#更新窗口数据
# ...
r += 1 # 右移窗口
需要注意的几个点：
1.什么时候需要need和window
一般来说，给了两个字符串或者数组s和t，就需要need和window；只给一个字符串或者数组s，然后求满足条件的最长、最短字串则不需要need和window
2.当right或者left移动的时候，即窗口增大或缩小的时候，应该更新那些数据
一般来说，如果字符加入窗口，则增大window计数器，如果字符移除窗口的时候则减少window计数器
3.什么时候应该收缩窗口
当valid满足了need则应该收缩窗口，收缩条件是关键的一步，具体要看实际情况。如果结果不正确很大概率是收缩条件没写正确。
4.最终结果应该在哪更新
一般是收缩窗口的时候更新最终结果，具体还需要根据实际情况更新，这也是关键的一步
用几道力扣的题目加深理解。
209. 长度最小的子数组
https://leetcode.cn/problems/minimum-size-subarray-sum/description/
先回答之前说的注意的点：
1.是否需要need和window
不需要，题目只给了一个数组
2.当right或者left移动的时候，即窗口增大或缩小的时候，应该更新那些数据
窗口增大需要增加和，窗口缩小需要减少和
3.什么时候应该收缩窗口
这题很好理解，当窗口的和大于等于target的时候需要收缩窗口
4.最终结果应该在哪更新
缩小窗口的时候就应该更新结果，即求最小子数组的长度
综上：
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
l = 0 # 左指针
r = 0 # 右指针
sum_num = 0 # 窗口的和
ans = float('inf') # 最终答案，因为是求最小长度，所以初始化为最大值
while r < len(nums): # 固定右指针遍历， 即右指针小于数组长度
sum_num += nums[r] # 窗口增大时增加和
while sum_num >= target: # 收缩条件
ans = min(ans, r - l + 1) # 更新最终结果
sum_num -= nums[l] # 收缩时减少和
l += 1 # 左指针移动
r += 1 # 右指针移动
return ans if ans != float('inf') else 0
76. 最小覆盖子串
https://leetcode.cn/problems/minimum-window-substring/description/
先回答之前说的注意的点：
1.是否需要need和window
需要，题目两个字符串
2.当right或者left移动的时候，即窗口增大或缩小的时候，应该更新那些数据
窗口增大需要判断是否增加window计数器并且是否需要增加valid值，窗口缩小需要判断是否需要减少window计数器并且是否需要减少valid值
3.什么时候应该收缩窗口
当valid值等于need的长度，就说明当前窗口已经覆盖了字符串t中所有的字符
4.最终结果应该在哪更新
缩小窗口的时候就应该更新结果，即求最小字串
此外有些关键点也需要注意
综上：
class Solution:
def minWindow(self, s: str, t: str) -> str:
window = {}
need = {}
for i in t:
need[i] = need.get(i, 0) + 1
l = 0
r = 0
valid = 0
lenght = float('inf') # 求最小字串，所以把字串的长度初始化为最大值
ans = '' # 最终结果
while r < len(s): # 固定移动右指针
c = s[r]
if c in need: # 只有当字符在need的时候才更新window计数器
window[c] = window.get(c, 0) + 1
if window[c] == need[c]: # 窗口内字符c的个数等于need中的个数才需要更新valid计数器
valid += 1
while valid == len(need): # 关键点，当valid等于need的长度，说明窗口中字符已经包含了t中的全部字符
if r - l < lenght: # 更新结果，因为找最小字串，所以判断当前窗口长度小于length
ans = s[l : r + 1] # 更新最终结果
lenght = r - l # 更新length，下一次就以它作为判断依据，看是否能找到比它更小的长度
d = s[l]
if d in need: # 缩小窗口时，当d在need中的时候就需要移除window计数器
if window[d] == need[d]:
'''关键点，需要先判断再减少window计数器的值，如果先减少window计数器的值则
第一次如果符合条件的话就漏减少了valid的值导致结果不正确'''
valid -= 1
window[d] -= 1
l += 1
r += 1
return ans
904. 水果成篮
https://leetcode.cn/problems/fruit-into-baskets/description/
这题简单理解就是在数组中找到一段连续的子数组，满足子数组内去重后数量小于等于2。
先回答之前说的注意的点：
1.是否需要need和window
不需要，只有一个数组；但是需要一个数据结构来记录窗口内数字的种类及个数。这里我选的是字典，也可以选择其他类型，比如Counter类
2.当right或者left移动的时候，即窗口增大或缩小的时候，应该更新那些数据
窗口增大需要增加window计数器，窗口缩小需要需要减少window计数器
3.什么时候应该收缩窗口
当window长度大于2时收缩窗口
4.最终结果应该在哪更新
缩小窗口完成后更新最终结果
综上：
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
window = {}
l = 0
r = 0
ans = 0
while r < len(fruits): # 固定右指针遍历
c = fruits[r]
window[c] = window.get(c, 0) + 1 # 进入窗口，增加window计数器
while len(window) > 2:
'''关键点，缩小条件，为什么是大于2的时候缩小，而不是等于2？
原因：如果等于2就缩小窗口，那么如果下一个字符串也满足条件是不是就漏掉了
例如：1 2 1 1
当窗口长度为2的时候，即此时窗口内有1 2，此时如果缩小窗口，那么后面的 1 1 就不在窗口中，这时漏掉了1 2 1 1 这个最长子串了'''
d = fruits[l]
window[d] -= 1 # 收缩时减少window计数器
if window[d] == 0: # 如果window[d] 等于0，就说明窗口内没有d了，此时需要在字典中移除d
del window[d]
l += 1
ans = max(ans, r - l + 1)
'''关键点，更新最终结果，为什么在外面更新，而不是在缩小窗口的时候更新？
因为缩小窗口条件是窗口长度大于2（相当于篮子数量大于2），而题目要求只有两个篮子，在里面更新会出现超过2的情况，不满足题目要求'''
r += 1
return ans
567. 字符串的排列
https://leetcode.cn/problems/permutation-in-string/description/
简单理解，在s2中找到一段连续的子串，包含s1中的字符且不能包含其他字符
先回答之前说的注意的点：
1.是否需要need和window
需要，有两个字符串
2.当right或者left移动的时候，即窗口增大或缩小的时候，应该更新那些数据
窗口增大需要判断是否增加window计数器并且是否需要增加valid值，窗口缩小需要判断是否需要减少window计数器并且是否需要减少valid值
3.什么时候应该收缩窗口
关键点，当窗口的长度等于s1的时候
4.最终结果应该在哪更新
缩小窗口时更新最终结果
综上：
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
window = {}
need = {}
for i in s1:
need[i] = need.get(i, 0) + 1
l = 0
r = 0
valid = 0
while r < len(s2): # 固定右指针遍历
c = s2[r]
if c in need:
window[c] = window.get(c, 0) + 1
if window[c] == need[c]: # 当窗口字符的个数和need相等是更新valid值
valid += 1
while r - l + 1 >= len(s1): # 关键点，当前窗口长度大于或者等于s1的长度时就说明可能找到了满足题意的字串，这时就需要缩小窗口更新最终结果
if valid == len(need): # 如果valid的长度等于need说明满足要求返回最终结果即可
return True
d = s2[l]
if d in need:
if window[d] == need[d]: #当窗口字符的个数和need相等是更新valid值
valid -= 1
window[d] -= 1 # 先判断再更新window计数器，否则第一次如果满足要求就会漏更新valid值
l += 1
r += 1
return False
438. 找到字符串中所有字母异位词
https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/
跟上面一题类似，不同的是上一题只需要找到一个符合题意的子串即可，这题需要存储所有符合题意的子串的起始索引
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
window = {}
need = {}
for i in p:
need[i] = need.get(i, 0) + 1
l = 0
r = 0
ans = [] # 存储最终答案
valid = 0
while r < len(s):
c = s[r]
if c in need:
window[c] = window.get(c, 0) + 1
if window[c] == need[c]:
valid += 1
while r - l + 1 == len(p): # 关键点，当前窗口长度等于（大于等于也是可以的）p的长度时，说明可能找到了符合条件的字串，需要缩小窗口
if valid == len(need): # 当valid等于need长度时说明找到了一个符合条件的子串，将该子串的起始索引更新到最终结果中
ans.append(l)
d = s[l]
if d in need:
if window[d] == need[d]:
valid -= 1
window[d] -= 1
l += 1
r += 1
return ans
3. 无重复字符的最长子串
https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
先回答之前说的注意的点：
1.是否需要need和window
不需要，只有一个字符串，但是需要一个数据结构记录当前窗口内各字符的数量
2.当right或者left移动的时候，即窗口增大或缩小的时候，应该更新那些数据
窗口增大需要增加window计数器，窗口缩小需要减少window计数器
3.什么时候应该收缩窗口
有重复字符时
4.最终结果应该在哪更新
缩小窗口完成后更新最终结果
综上：
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
window = {}
l = 0
r = 0
ans = 0
while r < len(s):
c = s[r]
window[c] = window.get(c, 0) + 1
while window[c] > 1: # 当window[c] 大于1时，说明有重复的字符，所以需要缩小窗口
d = s[l]
window[d] -= 1
l += 1
ans = max(ans, r - l + 1) # 在窗口缩小完成后再更新最终结果，确保不会出现窗口内有重复字符的情况
r += 1
return ans
标签：窗口,更新,window,valid,ans,need,滑动 From： https://www.cnblogs.com/xiao-bai000/p/17032984.html