【经典LeetCode算法题目专栏分类】【第8期】滑动窗口：最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串

left =?0

right ?=?0

while??right <?len(s):

????# 右指针右移增大窗口

????window.add(s[right])

????right ?+=?1

????while?isvalid:

????????# 当满足某种条件时开始从左边收缩窗口

????????window.remove(s[left])

????????left +=?1

def?slidingWindow(s,?t):

????from?collections import?defaultdict

????# defaultdict(int)对于不存在的键默认值为0，

????# 可以直接进行window[c] += 1的操作，免去了判断过程

????window =?defaultdict(int)

????needs??=?defaultdict(int)

????left =?0

????right =?0

????for?c in?t:

????????needs[c]?+=?1

????while?right <?len(s):

????????# c1为移入窗口的字符

????????c1 =?s[right]

????????# 窗口右移

????????right +=?1

????????# 进行窗口内数据的相关操作

????????# TODO

????????# 判断左侧窗口是否要收缩

????????while?window needs shrink:

????????????# c2为将要移出窗口的字符

????????????c2 =?s[left]

????????????# 左指针右移，收缩窗口

????????????left +=?1

????????????# 进行窗口内数据的相关操作

????????????# TODO

class?Solution:

????def?minWindow(self,?s:?str,?t:?str)?->?str:

????????from?collections import?defaultdict

????????needs =?defaultdict(int)

????????window =?defaultdict(int)

????????left =?0

????????right =?0

????????count =?0?#window中满足条件的字符数

????????start =?0 #记录最小子串的起始位置

????????min_len =?float('inf') #记录最小子串的长度

????????for?c in?t:

????????????needs[c]?+=?1

????????while?right <?len(s):

????????????c1 =?s[right]

????????????right +=?1

????????????if??c1 in?needs:

????????????????window[c1]?+=?1

????????????????if?window[c1]?==?needs[c1]:

????????????????????count +=?1

????????????while?count ==?len(needs):

????????????????# 更新最小覆盖子串

????????????????if?right -?left <?min_len:

????????????????????start =?left

????????????????????min_len =?right -?left

????????????????c2 =?s[left]

????????????????left +=?1

????????????????if?c2 in?needs:

????????????????????window[c2]?-=?1

????????????????????if?window[c2]?<?needs[c2]:

????????????????????????count -=?1

????????if?min_len ==?float('inf'):

????????????return?''

????????else:

????????????return?s[start:start+min_len]

class?Solution:

????def?checkInclusion(self,?s1:?str,?s2:?str)?->?bool:

????????from?collections ?import?defaultdict

????????needs =?defaultdict(int)

????????for?c in?s1:

????????????needs[c]?+=?1

????????window =?defaultdict(int)

????????left =?0

????????right =?0

????????count =?0

????????while?right <?len(s2):

????????????c1 =?s2[right]

????????????right +=?1

????????????if?c1 in?needs:

????????????????window[c1]?+=?1

????????????????if?window[c1]?==?needs[c1]:

????????????????????count +=?1

????????????while?count ==?len(needs):

????????????????if?right -?left ==?len(s1):

????????????????????# 如果子串长度与s1相等则包含

????????????????????return?True

????????????????c2 =?s2[left]

????????????????if?c2 in?needs:

????????????????????window[c2]?-=?1

????????????????????if?window[c2]?<?needs[c2]:

????????????????????????count -=?1

????????????????left +=?1

????????return?False

class?Solution:

????def?findAnagrams(self,?s:?str,?p:?str)?->?List[int]:

????????from?collections import?defaultdict

????????needs =?defaultdict(int)

????????window =?defaultdict(int)

????????left =?0

????????right =?0

????????count =?0

????????res =?[]

????????for?c in?p:

????????????needs[c]?+=?1

????????while?right <?len(s):

????????????c1 =?s[right]

????????????if?c1 in?needs:

????????????????window[c1]?+=?1

????????????????if?window[c1]?==?needs[c1]:

????????????????????count +=?1

????????????right +=?1

????????????while?count ==?len(needs):

????????????????if?right -?left ==?len(p):

????????????????????res.append(left)

????????????????c2 =?s[left]

????????????????if?c2 in?needs:

????????????????????window[c2]?-=?1

????????????????????if?window[c2]?<?needs[c2]:

????????????????????????count -=?1

????????????????left +=?1

????????return?res

class?Solution:

????def?lengthOfLongestSubstring(self,?s:?str)?->?int:

????????max_len =?0

????????left =?0

????????right =?0

????????n =?len(s)

????????from?collections import?defaultdict

????????window =?defaultdict(int)

????????while?right <?n:

????????????c1 =?s[right]

????????????right +=?1

????????????window[c1]?+=?1

????????????while?window[c1]?>?1:

????????????????c2 =?s[left]

????????????????left +=?1

????????????????window[c2]?-=?1

????????????max_len =?max(max_len,?right -?left)

????????return?max_len