76、最小覆盖子串

基本思想：

用left,right表示滑动窗口的左边界和右边界，通过改变left,right来扩展和收缩滑动窗口，可以想象成一个窗口在字符串上游走，当这个窗口包含的元素满足条件，即包含字符串T的所有元素，记录下这个滑动窗口的长度right-left+1，这些长度中的最小值就是要求的结果。

1.不断增加right，扩大窗口，直到窗口中的字符符合要求，包含了T中所有字符

2.停止增加right，增加left，缩小窗口，直到窗口中的字符再扔一个就不再符合要求，记录下最小值

3.继续增加left到刚刚不符合要求，重复步骤1,2，也就是继续增加right到下一次符合要求，再到下一次记录最小值，

比这两次最小值谁更小

具体实现：

need中存放的是所需要的元素个数

随着right增加所需要的元素个数会慢慢减少

知道窗口中不再需要任何元素，因为窗口中已经包含了所有需要的元素

 

代码：

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need=collections.defaultdict(int) #计数器
        for c in t:
            need[c] += 1 #记录所需字符的个数
        needCnt=len(t) #所需字符的总个数
        left = 0 #窗口的开端
        res=(0,float('inf')) #记录最小窗口 刚开始是0到无穷大
        for right,c in enumerate(s): #遍历原字符串
            if need[c]>0: #遍历到的这个字符串在need中如果大于0，说明是目标字符
                needCnt-=1 #还需要的字符个数-1
            need[c]-=1 #在need中不管是不是所要的都要-1
            if needCnt==0:       #完成步骤一：滑动窗口包含了所有T元素
                while True:      #步骤二：增加i，排除多余元素
                    c=s[left]     #从窗口左端开始一个一个排除不需要的元素
                    if need[c]==0: #刚刚好排除了左端所有没用的元素
                        break  #现在的窗口第一个元素和最后一个元素保证都是所需要的元素
                    need[c]+=1
                    left+=1
                if right-left < res[1]-res[0]:   #记录结果，比较哪次的符合要求的窗口最小
                    res=(left,right)
                need[s[left]]+=1  #步骤三：i增加一个位置，寻找新的满足条件滑动窗口
                needCnt+=1 #开始不要第一个所需要的元素往后走了
                left+=1
        return '' if res[1]>len(s) else s[res[0]:res[1]+1]    #如果res始终没被更新过，代表无满足条件的结果