滑动窗口算法技巧【Python】

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

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