力扣76题、567题、438题、3题（滑动窗口算法）

76、最小覆盖子串

基本思想：

1、用left,right表示滑动窗口的左边界和右边界，通过改变left,right来扩展和收缩滑动窗口，

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

3、停止增加right，增加left，缩小窗口，直到窗口中的字符符合要求

4、重复步骤2 3 直到right走到字符串的尽头

具体实现：

need，window相当于计数器，记录下t中字符出现次数和“窗口”中的相应字符出现次数

valid变量表示窗口中满足need条件的字符种类数

valid == len（need）说明窗口中已经满足有t里面所有字符，但是需要找最小的字符串

1、移动right扩大窗口，加入字符时，更新Window计数器，valid

2、窗口暂停扩大时，是因为窗口中已经包含了t中所有字符

3、移动left缩小窗口，移出字符时，更新Window计数器

4、需要的结果是最短子串，在缩小窗口时进行更新

代码：

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need=collections.Counter(t)
        window=collections.Counter()
        left,right,valid,slen,nlen=0,0,0,len(s),len(need)
        start,minlen=0,float('inf') #初始化最小长度是无穷大
        while right<slen:
            c=s[right]
            right+=1
            if c in need:
                window[c]+=1
                if window[c]==need[c]:
                    valid+=1
            while valid==nlen: #窗口包含子串
                if right-left<minlen: #比哪次的长短端，记录下来
                    start=left      
                    minlen=right-left
                d=s[left]
                left+=1
                if d in need:
                    if window[d]==need[d]:
                        valid-=1
                    window[d]-=1
        return '' if minlen==float('inf') else s[start:start+minlen]

567、字符串排列

基本思想：

滑动窗口算法

具体实现：

1、各种排列的长度是一样的，窗口暂停扩大时，就是窗口已经到了s1的长度

上题窗口暂停扩大是因为，窗口中包含了所有想要的字符，

这次也没有包含也可以暂停，只要长度达到就暂停，所以往后走的窗口的长度是固定的

2、valid == len（need），说明窗口中是想要的结果，直接返回true

代码：

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        need=collections.Counter(s1)
        window=collections.Counter()
        left,right,valid,s1len,nlen=0,0,0,len(s2),len(need)
        while right<s1len:
            c=s2[right]
            right+=1
            if c in need:
                window[c]+=1
                if window[c]==need[c]:
                    valid+=1
            while right-left >= len(s1): # right指针是先给c，再往后移，说明right指针当前字符往后一个
                if valid == nlen: #left指针初始化为0，正好他俩减就是窗口的长度
                    return True
                d=s2[left]
                left+=1
                if d in need:
                    if window[d]==need[d]:
                        valid-=1
                    window[d]-=1
        return False

438、找所有字母异位词

基本思想：

上道题是问是否存在，

这道题是如果存在要返回起始索引

具体实现：

只要在上道题返回True的地方，记录索引就好

代码：

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        need = collections.Counter(p)
        window = collections.Counter()
        left,right,valid,slen,plen = 0,0,0,len(s),len(p)
        res = []
        while right < slen:
            c = s[right]
            right += 1
            if c in need:
                window[c] += 1
                if window[c] == need[c]:
                    valid += 1
            while right-left >= plen:
                if valid == len(need):
                    res.append(left)
                d = s[left]
                left += 1
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
        return res

3、最长无重复子串

基本思想：

滑动窗口算法

具体实现：

1、不需要need和valid，就他一个人玩

只要更新窗口内数据和计数器window就可以

2、window[c]大于1。说明有重复字符，不符合条件，移动left，缩小窗口

3、更新结果时需要在收缩窗口之后，因为收缩完窗口后，窗口中的字符串是无重复的

代码：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        window = collections.Counter()
        left,right,res = 0,0,0
        while right < len(s):
            c= s[right]
            right += 1
            window[c] += 1
            while window[c]>1:
                d = s[left]
                left += 1
                window[d] -= 1
            res = max(res,right-left)
        return res