leetcode刷题的滑动窗口技巧【Python】
滑动窗口主要左右指针的应用，其中难点判断什么条件下缩小窗口，主要还是细节问题。
以下4道题举例说明：
76.最小覆盖子串（困难）
image.png
题目： 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
示例 2：
输入：s = “a”, t = “a”
输出：“a”
def min_window(s,t):
"""左右指针"""
#构造目标字符串的字典
need ={}
for i in range(len(t)):
if t[i] in need.keys():
need[t[i]] += 1
else:
need[t[i]] = 1
l,r =0,0
valid = 0#记录满足条件的字符个数
window = {}
start,lens=0,float('inf')
while r<len(s):
#c是将移入窗口的字符
c = s[r]
r += 1
if c in need.keys() and c in window.keys() :
window[c] += 1
if window[c]==need[c]:
valid += 1
elif c in need.keys() and c not in window.keys():
window[c] = 1
if window[c]==need[c]:
valid += 1
#判断左窗口是否要收缩
while valid==len(need):
if r-l<lens:
start = l
lens = r-l
d= s[l]
l += 1
if d in need.keys():
if window[d]==need[d]:
valid -= 1
window[d] -= 1
return '' if lens==float('inf') else s[start:start+lens]
s = 'ADOBECODEBANC'
t = 'ABCB'
min_window(s,t)
其他解法供参考
def minWindow(s, t):
from collections import defaultdict
win = defaultdict(int)
t_dict = defaultdict(int)
for i in t:
t_dict[i] += 1
# 定义指针
left = 0
right = 0
# 初始化最小长度
min_len = float('inf')
# chr_count 用以表示滑动窗口包含字符数
chr_count = 0
# 最小子串起始位置
begin = 0
# s 长度
s_len = len(s)
# t 长度
t_len = len(t)
while right < s_len:
# 移动窗口，
if t_dict[s[right]] == 0:
right += 1
continue
# 滑动窗口包含 T 字符数，当超过 T 其中字符个数时不在增加
if win[s[right]] < t_dict[s[right]]:
chr_count += 1
win[s[right]]+=1
right+=1
# 当窗口包含 T 所有的字符时，缩小窗口
while chr_count == t_len:
# 这里更新子串的其实位置和长度
if right-left < min_len:
begin = left
min_len = right - left
# 缩小窗口
if t_dict[s[left]] == 0:
left += 1
continue
# 这里表示出窗时，窗口所包含 T 的字符刚好等于 T 中字符的个数
# 这个时候再移动，窗口就不满足包含 T 所有字符的条件
# 这里 chr_count - 1 ，循环结束
if win[s[left]] == t_dict[s[left]]:
chr_count -= 1
win[s[left]]-=1
left += 1
return "" if min_len == float('inf') else s[begin:begin+min_len]
s = 'ADOBECODEBANC'
t = 'ABBC'
minWindow(s,t)
def minWindow( s, t):
from collections import Counter
t = Counter(t)
lookup = Counter()
start = end = 0
min_len = float("inf")
res = ""
while end < len(s):
lookup[s[end]] += 1
end += 1
while all(map(lambda x: lookup[x] >= t[x], t.keys())):
if end - start < min_len:
res = s[start:end]
min_len = end - start
lookup[s[start]] -= 1
start += 1
return res
s = 'ADOBECODEBANC'
t = 'ABBC'
minWindow(s,t)
567.字符串的排列（中等）
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).
示例2:
输入: s1= “ab” s2 = “eidboaoo”
输出: False
注意：
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间
思路：
这里需要注意的点是这里问的是s2中是否存在一个子串，包含s1中所有字符但不包含其他字符
s1是可以包含重复字符的。
然后还是套用框架，并做小修。
def min_window(s,t):
"""左右指针"""
#构造目标字符串的字典
need ={}
for i in range(len(t)):
if t[i] in need.keys():
need[t[i]] += 1
else:
need[t[i]] = 1
l,r =0,0
valid = 0#记录满足条件的字符个数
window = {}
start,lens=0,float('inf')
while r<len(s):
#c是将移入窗口的字符
c = s[r]
r += 1
if c in need.keys() and c in window.keys() :
window[c] += 1
if window[c]==need[c]:
valid += 1
elif c in need.keys() and c not in window.keys():
window[c] = 1
if window[c]==need[c]:
valid += 1
#判断左窗口是否要收缩
while r-l>=len(t):
if valid==len(need):
return True
d= s[l]
l += 1
if d in need.keys():
if window[d]==need[d]:
valid -= 1
window[d] -= 1
return False
s = 'ADOBECODEBANC'
t = 'AB'
min_window(s,t)
438.找到字符串中所有字母异位词（中等）
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:
输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。 起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。 起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母
思路：与567题目基本一致。
def min_window(s,t):
"""左右指针"""
#构造目标字符串的字典
need ={}
for i in range(len(t)):
if t[i] in need.keys():
need[t[i]] += 1
else:
need[t[i]] = 1
l,r =0,0
valid = 0#记录满足条件的字符个数
window = {}
start=[]
while r<len(s):
#c是将移入窗口的字符
c = s[r]
r += 1
if c in need.keys() and c in window.keys() :
window[c] += 1
if window[c]==need[c]:
valid += 1
elif c in need.keys() and c not in window.keys():
window[c] = 1
if window[c]==need[c]:
valid += 1
#判断左窗口是否要收缩
while r-l>=len(t):
if valid==len(need):
start.append(l)
d= s[l]
l += 1
if d in need.keys():
if window[d]==need[d]:
valid -= 1
window[d] -= 1
return start
s = 'cbaebabacd'
t = 'abc'
min_window(s,t)
3.无重复字符的最长子串（中等）
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
def min_window(s):
"""左右指针"""
#构造目标字符串的字典
# need ={}
# for i in range(len(t)):
# if t[i] in need.keys():
# need[t[i]] += 1
# else:
# need[t[i]] = 1
l,r =0,0
res = 0#记录满足条件的字符个数
window = {}
# start=[]
while r<len(s):
#c是将移入窗口的字符
c = s[r]
r += 1
if c in window.keys() :
window[c] += 1
elif c not in window.keys():
window[c] = 1
#判断左窗口是否要收缩
while window[c]>1:
d= s[l]
l += 1
window[d] -= 1
res = max(res,r-l)
return res
s = 'abcabcbb'
#t = 'abc'
min_window(s)
其他优化解法【推荐】：
def min_window(s):
"""左右指针"""
#构造目标字符串的字典
res =tmp= 0#记录满足条件的字符个数(间隔数)
window = {}
for r in range(len(s)):
#c是将移入窗口的字符
c = s[r]
l = window.get(c,-1)
window[c]=r
tmp= tmp+1 if tmp<r-l else r-l
res=max(tmp,res)
return res
s = 'apwpwkew'
min_window(s)
