滑动窗口算法技巧【Python】

大家好，欢迎来到IT知识分享网。

这篇文章通过几道题目来总结滑动窗口算法的解题模板与技巧。滑动窗口算法是双指针技巧的最高境界，掌握了滑动窗口的解题模板可以轻松解决一系列字符串匹配的问题。
文章开头直接给出滑动窗口解题的模板

left, right = 0, 0
win = []
while right < len(s):
	win.append(s[right])
	right += 1
	
	while isValid(win):
		win.pop(0)
		left += 1
	

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。

输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的连续子数组。

用窗口win保存当前的子数组，当移动right进入win满足条件时，更新结果并缩小左边界left。注意这里是正整数数组，所以满足的条件应该为sum(win)>=s。如果把正整数条件去掉，就不能用这个滑动窗口算法模板做了，因为你不知道什么条件下（是大于?等于?还是小于）去滑动窗口。

    def minSubArrayLen(self, s, nums):
        """ 用滑动窗口的模板来解题, 时间复杂度o(n) 空间复杂度o(1) """
        left, right = 0, 0
        win = []
        ans = len(nums) + 1
        while right < len(nums):
            win.append(nums[right])
            right += 1

            while sum(win) >= s:  # 维护的滑动窗口需要满足的条件
                ans = min(ans, right-left)
                win.pop(0)
                left += 1

        return 0 if ans == len(nums) + 1 else ans

如果是求最短的和为定值的子数组，那么只需要把模板中的isValid改成sum(win) > s，然后再次进行判断。

    def minSubArrayEq(self, s, nums):
        """ 寻找子序列和为s的最短子序列 """
        left, right = 0, 0
        win = []
        ans = 0x3f3f3f3f

        while right < len(nums):
            win.append(nums[right])
            right += 1

            while sum(win) > s:
                win.pop(0)
                left += 1
            if sum(win) == s:
                ans = min(ans, len(win))

        return 0 if ans == 0x3f3f3f3f else ans

3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

需要建立一个map保存当前窗口win的字符集，当加入right之后如果map中存在重复元素，那么缩小左边界直到right这个元素只出现了一次。

    def lengthOfLongestSubstring(self, s):
        """ 3. 无重复字符的最长子串 """
        left, right = 0, 0
        win = []
        map = dict()
        res = 0

        while right < len(s):
            cur = s[right]
            win.append(s[right])
            if s[right] in map:
                map[s[right]] += 1
            else:
                map[s[right]] = 1
            right += 1

            # 如果map中存在重复字符，则缩小左边界，直到当前cur字符在map中仅出现一次
            while map[cur] > 1:
                map[s[left]] -= 1
                win.pop(0)
                left += 1
            res = max(res, right - left)
        return res

76. 最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

输入: S = “ADOBECODEBANC”, T = “ABC”
输出: “BANC”
说明：
如果 S 中不存这样的子串，则返回空字符串 “”。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

关键在于isValid的定义：当win包含t串的所有字符，left才左移。所以isValid应该是判断win是否包含t的所有字符。通过分别定义两个串的两个map即可实现，但是这边注意不需要在函数内部定义新map，直接定义关于当前窗口win和t串的map，然后在滑动窗口的同时更新map即可。

    def minWindow(self, s, t):
        """ 76. 最小覆盖子串：在字符串 S 里面找出：包含 T 所有字符的最小子串。 """
        left, right = 0, 0
        win = []
        ans = 0x3f3f3f3f
        ansleft, ansright = -1, -1

        # 两个map，来判断字符的覆盖情况
        map_t = dict()
        map_win = dict()
        for i in range(len(t)):
            if t[i] in map_t:
                map_t[t[i]] += 1
            else:
                map_t[t[i]] = 1

        def isValid(map_win, map_t):
            """ 判断win是否包含t的所有字符 """
            for key, value in map_t.items():
                if key not in map_win:
                    return False
                if map_win[key] < value:
                    return False
            return True

        while right < len(s):
            win.append(s[right])
            # 多出来的这块是更新map_win
            if s[right] in map_win:
                map_win[s[right]] += 1
            else:
                map_win[s[right]] = 1
            right += 1

            while isValid(map_win, map_t):
                if right - left < ans:
                    ans = right - left
                    ansleft = left
                    ansright = right - 1
                # 删除left元素需要更新map_win
                map_win[s[left]] -= 1
                if map_win[s[left]] == 0:  # 删除这个键
                    del map_win[s[left]]
                win.pop(0)
                left += 1

        if ans == 0x3f3f3f3f:
            return ""
        else:
            return s[ansleft:ansright + 1]

438. 找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：
字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。

输入:
s: “cbaebabacd” p: “abc”
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的字母异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的字母异位词。

这道题只需要在上面那道题的基础上改：将更新结果的判断条件改成len(win)==len(t)即可

    def findAnagrams(self, s, p):
        """ 438. 找到字符串中所有字母异位词 """
        left, right = 0, 0
        win = []
        res = []

        # 两个map，来判断字符的覆盖情况
        map_p = dict()
        map_win = dict()
        for i in range(len(p)):
            if p[i] in map_p:
                map_p[p[i]] += 1
            else:
                map_p[p[i]] = 1

        def isValid(map_win, map_t):
            """ 判断win是否包含t的所有字符 """
            for key, value in map_t.items():
                if key not in map_win:
                    return False
                if map_win[key] < value:
                    return False
            return True

        while right < len(s):
            win.append(s[right])
            # 多出来的这块是更新map_win
            if s[right] in map_win:
                map_win[s[right]] += 1
            else:
                map_win[s[right]] = 1
            right += 1

            while isValid(map_win, map_p):
                if right - left == len(p):  # 长度相等时保存结果
                    res.append(left)
                # 删除left元素需要更新map_win
                map_win[s[left]] -= 1
                if map_win[s[left]] == 0:  # 删除这个键
                    del map_win[s[left]]
                win.pop(0)
                left += 1

        return res