滑动窗口算法框架
扩大窗口：寻找可行解
缩小窗口：找到最优解
def slidingWindows(s,t): # source, target
need = collections.Counter(t) # 需要出现的次数
windows = dict.fromkeys(need.keys(),0) # 窗口中出现的次数
left = right = 0 # 左右指针表示窗口[left,right)
valid = 0 # 表示窗口中满足need条件的字符个数
while right < len(s):
c = s[right] # 移入窗口的字符
right += 1
# 窗口内数据的更新
if c in need:
windows[c] += 1
if windows[c] == need[c]:
valid += 1
print(letf,right) # debug输出位置
while shrink: # 左窗口需要收缩
d = s[left] # 移出窗口的字符
left += 1
# 窗口内数据的更新
if d in need:
if windows[d] == need[d]:
valid -= 1
windows[d] -= 1思考四个问题：
1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？
2、什么条件下，窗口应该暂停扩大，开始移动 left 缩小窗口？
3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
最小覆盖子串（困难）
class Solution:
def minWindow(self, s: str, t: str) -> str:
need = collections.Counter(t)
windows = dict.fromkeys(need.keys(),0)
left = right = 0
valid = 0 # 满足need的个数
minstr = s + 'A'
while right < len(s):
c = s[right]
right += 1
# 窗口内数据更新
if c in need:
windows[c] += 1
if windows[c] == need[c]:
valid += 1
while valid >= len(need): # 收缩窗口
minstr = s[left:right] if len(s[left:right]) < len(minstr) else minstr
d = s[left] # 移出字符
left += 1
# 窗口内数据更新
if d in need:
if windows[d] == need[d]:
valid -= 1
windows[d] -= 1
if minstr == s + 'A': return ""
return minstr