leetcode滑动窗口练习题
滑动窗口适合处理一部分连续子串问题。穷举子串需要枚举起点和终点，仅区间数量就有 ，逐段检查还会增加开销。若能随着左右边界移动增量维护窗口状态，就可以避免反复检查整段子串。虽然代码里可能嵌套两个循环，但左右指针都只向前移动；窗口数据的单次更新为常数开销时，整体时间复杂度为 。
下面是滑动窗口的伪代码框架，其中的省略内容需要根据题目补全：
# 滑动窗口算法伪码框架
def slidingWindow(s: str):
# 用合适的数据结构记录窗口中的数据，根据具体场景变通
# 比如说，我想记录窗口中元素出现的次数，就用 map
# 如果我想记录窗口中的元素和，就可以只用一个 int
window = ...
left, right = 0, 0
while right < len(s):
# c 是将移入窗口的字符
c = s[right]
window.add(c)
# 增大窗口
right += 1
# 进行窗口内数据的一系列更新
...
# *** debug 输出的位置 ***
# 注意在最终的解法代码中不要 print
# 因为 IO 操作很耗时，可能导致超时
# print(f"window: [{left}, {right})")
# ***********************
# 判断左侧窗口是否要收缩
while left < right and window needs shrink:
# d 是将移出窗口的字符
d = s[left]
window.remove(d)
# 缩小窗口
left += 1
# 进行窗口内数据的一系列更新
...写滑动窗口时，我会先考虑三个问题：
1、什么时候移动 right 扩大窗口？新字符加入后，需要更新哪些数据？
2、什么时候移动 left 缩小窗口？字符移出后，需要更新哪些数据？
3、在哪个时机更新答案？
这些问题能帮助确定窗口的维护方式。还需要结合题目条件判断：边界是否可以只向前移动，移除或加入元素后，窗口状态能否及时更新。
76. 最小覆盖子串
这道题用 need 统计目标串中每个字符需要出现的次数，用 window 统计当前窗口的字符次数。代码中的 vaild 记录已有多少种字符达到了所需次数，left 和 right 则表示窗口的左右边界。满足所有字符要求后，尝试缩小窗口，并记录更短的可行答案。
class Solution:
def minWindow(self, s: str, t: str) -> str:
window = dict()
need = dict()
# 把目标串存到目标窗口
for i in t:
need[i] = need.get(i, 0) + 1
vaild = 0
left = right = 0
length = float("inf")
res = ""
while right < len(s):
c = s[right]
right += 1
# 如果字符在need窗口里面就让计数器+1
if c in need:
window[c] = window.get(c, 0) + 1
# 如果这个字符满足条件了，就让vaild+1
if window[c] == need[c]:
vaild += 1
# 当vaild和目标窗口长度相同，就代表所有元素都满足条件了，尝试缩小窗口
while vaild == len(need):
# 此时的子串就是一个符合条件的子串，尝试更新答案
if length > right - left:
res = s[left:right]
length = right - left
c = s[left]
left += 1
# 缩小窗口，更新相关的数据。
if c in need:
if window[c] == need[c]:
vaild -= 1
window[c] -= 1
return res567. 字符串的排列
这里维护的是长度等于 s1 的定长窗口。内层我用了 if：每加入一个字符，窗口长度最多比目标长度多一格，检查后移出最左侧一个字符即可。当窗口长度达到 s1 的长度时，如果每种字符的数量都满足要求，就找到了 s1 的一种排列；否则继续向右滑动。
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
need = dict()
window = dict()
for i in s1:
need[i] = need.get(i, 0) + 1
vaild = left = right = 0
while right < len(s2):
c = s2[right]
right += 1
if c in need:
window[c] = window.get(c, 0) + 1
if window[c] == need[c]:
vaild += 1
if right - left >= len(s1):
if vaild == len(need):
return True
c = s2[left]
left += 1
if c in need:
if window[c] == need[c]:
vaild -= 1
window[c] -= 1
return False438. 找到字符串中所有字母异位词
思路与第 567 题相同，仍然维护定长窗口。区别是不能找到一个就返回，而要把每个符合条件的窗口起始索引加入结果。
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
need = dict()
windows = dict()
vaild = left = right = 0
res = []
for i in p:
need[i] = need.get(i, 0) + 1
while right < len(s):
c = s[right]
right += 1
if c in need:
windows[c] = windows.get(c, 0) + 1
if windows[c] == need[c]:
vaild += 1
if right - left >= len(p):
if vaild == len(need):
res.append(left)
c = s[left]
left += 1
if c in need:
if windows[c] == need[c]:
vaild -= 1
windows[c] -= 1
return res3. 无重复字符的最长子串
本题不需要 need，只统计当前窗口中各字符的次数。每次加入新字符后，如果它出现了不止一次，就移动左边界，直到重复被消除。内层 while 结束时，当前窗口不含重复字符，再用窗口长度更新答案。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
left = right = 0
window = dict()
length = 0
while right < len(s):
c = s[right]
right += 1
window[c] = window.get(c, 0) + 1
while window[c] >= 2:
new_c = s[left]
left += 1
window[new_c] -= 1
if right - left > length:
length = right - left
return length谢谢你读到这里。 ✧
下一篇文章leetcode链表双指针练习题