一、滑动窗口是什么
滑动窗口是双指针套路的一种,一般用于求解满足要求的子串或一段连续数组
在数据或字符串中定义两个指针,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