最小覆盖子串

1、题目

图1

2、题解

滑动窗口

用\(i、j\)表示滑动窗口的左右边界，通过改变\(i，j\)去增大或收缩滑动窗口，当窗口包含的元素满足调节，记录下此时滑动窗口的长度，这些长度中的最小值就是要求的结果

• 增加\(j\)使得窗口增大，直到窗口包含了t的所有元素。
• 增加\(i\)使得窗口缩小，将不必要的元素排除在外，直到碰到一个必须包含的元素，记录此时滑动窗口的长度，并保存最小值。
• 令i继续增加位置，回到第一步，寻找心的满足条件的滑动窗口，直到j超出了字符串s的范围。

可以用一个字典\(dict\)来表示当前滑动窗口中需要的各元素的数量，用t中的元素初始化这个\(dict\)。当滑动窗口中包含某个元素，就令\(dic\)t中该元素数量减1；当窗口移除某个元素，就让\(dict\)中该元素的数量加1。

如果每次通过遍历\(dict\)来判断滑动窗口是否包含了所有元素会耗费\(O(k)\)的时间复杂度，我们可以通过一个额外变量\(dictCnt\)来记录所需元素的总数量，通过该变量的大小来判断窗口是否满足条件。

图2

class Solution:
   def minWindow(self, s: str, t: str) -> str:
        need=collections.defaultdict(int)
        for c in t:
            need[c]+=1
        needCnt=len(t)
        i=0
        res=(0,float('inf'))
        for j,c in enumerate(s):
            if need[c]>0:
                needCnt-=1
            need[c]-=1
            if needCnt==0:       #步骤一：滑动窗口包含了所有T元素
                while True:      #步骤二：增加i，排除多余元素
                    c=s[i] 
                    if need[c]==0:
                        break
                    need[c]+=1
                    i+=1
                if j-i<res[1]-res[0]:   #记录结果
                    res=(i,j)
                need[s[i]]+=1  #步骤三：i增加一个位置，寻找新的满足条件滑动窗口
                needCnt+=1
                i+=1
        return '' if res[1]>len(s) else s[res[0]:res[1]+1]    #如果res始终没被更新过，代表无满足条件的结果