滑动窗口总结

分为不定长滑窗和定长滑窗：
不定长滑窗：最标准形式，针对问题可适当简化。
主要是缩小窗口的时机：刚好满足条件时缩小，看是否左边有不需要的

while vaild == len(need):             #都满足之后尝试缩小
1

def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        need = collections.Counter(t)  #记录需要的元素及个数
        win = dict()                   #记录找到的元素及个数
        l,r = 0,0                      #指针都指向0
        min_len = len(s)+1             #记录最小长度
        vaild = 0                      #记录满足的个数
        for r in range(len(s)):
            if s[r] in need:           #这个r满足条件，这里别判断是否在字符串中，时间复杂度会大幅提升
                win[s[r]] = win.get(s[r], 0) + 1  #更新win字典
                if win[s[r]] == need[s[r]]:       #这个元素刚好满足要求了
                    vaild += 1                    #满足的个数加一
            while vaild == len(need):             #都满足之后尝试缩小
                if r-l+1 < min_len:               #先更新最小长度
                    min_len = r-l+1
                    start = l
                if s[l] in win:                   #注意这里判断是否在字典中，别判断是否在字符串中，时间复杂度会大幅提升
                    if win[s[l]] == need[s[l]]:    #如果这个元素不满足了（注意这里使用==之后再更新，不能用<，因为重复的会减小几次）
                        vaild -= 1                #满足的个数减一
                    win[s[l]] -= 1                #更新win
                l += 1
        if min_len == len(s) + 1:
            return ""
        return s[start:start+min_len]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

定长滑动窗口：缩小窗口的时机是窗口大小达到了

def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        need = collections.Counter(s1)
        l = 0
        valid = 0
        win = dict()
        for r in range(len(s2)):
            if s2[r] in need:
                win[s2[r]] = win.get(s2[r],0) + 1
                # if win[s2[r]] == need[s2[r]]:
                #     valid += 1
            while r-l+1 == len(s1):
                if win == need:
                    return True
                if s2[l] in win:
                    # if win[s2[l]] == need[s2[l]]:
                    #     valid -= 1
                    win[s2[l]] -= 1
                l += 1
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24