滑动窗口刷题指南

一、滑动窗口解题框架

# 滑动窗口算法框架
class Solution:def slidingWindow(self, s: str, p: str):left = right = 0needs, window = {}, {}match = 0for v in p: needs[v] = needs.get(v, 0) + 1while right < len(s):cur = s[right]# 进行窗口内数据的一系列更新if needs.get(cur):window[cur] = window.get(cur, 0) + 1if window[cur] == needs[cur]: match += 1right += 1# 判断左侧窗口是否要收缩while (window needs shrink):# 当窗口符合条件时，执行相应操作cur = s[left]# 进行窗口内数据的一系列更新if needs.get(cur):if window[cur] == needs[cur]: match -= 1window[cur] -= 1left += 1

二、刷题指南

1、最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

import math
class Solution:def minWindow(self, s: str, t: str) -> str:left = right = 0needs, window = {}, {}smallest_len, smallest_str = math.inf, ""# 记录 window 中已经有多少字符符合要求了match = 0for v in t: needs[v] = needs.get(v, 0) + 1while right < len(s):cur = s[right]if needs.get(cur):window[cur] = window.get(cur, 0) + 1# 注意这里是 ==, 不是>=, 因为match是算A、B、C存在即符合条件# 如果>=,两个B一个C没有A, match也是3,但其实只有一个A、一个B、一个C才算matchif window[cur] == needs[cur]: match += 1# 注意这里的right其实是多加了1的right += 1 while match == len(needs):# 因为上面right多加1，因此原本这里的right - left + 1, 这里只需要right - left即可cur_len = right - leftif cur_len < smallest_len:smallest_len = cur_len# 因为上面right多加1，因此原本这里的s[left:right + 1], 这里只需要s[left:right]即可smallest_str = s[left:right]cur = s[left]if needs.get(cur):if window[cur] == needs[cur]: match -= 1window[cur] -= 1left += 1return smallest_str

2、找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

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

class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:left = right = 0needs, window = {}, {}res = []match = 0 for v in p: needs[v] = needs.get(v, 0) + 1while right < len(s):cur = s[right]# 进行窗口内数据的一系列更新if needs.get(cur):window[cur] = window.get(cur, 0) + 1if window[cur] == needs[cur]: match += 1right += 1# 判断左侧窗口是否要收缩# 这个题比较特殊可以直接if, 也可以和解题框架保持一致使用：while (right - left) == len(p):if (right - left) == len(p):# 当窗口符合条件时，把起始索引加入 resif match == len(needs):res.append(left)cur = s[left]# 进行窗口内数据的一系列更新if needs.get(cur):if window[cur] == needs[cur]: match -= 1window[cur] -= 1left += 1return res

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

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

示例 1:

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

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:left = right = 0window = {}longest_len = 0while right < len(s):r = s[right]window[r] = window.get(r, 0) + 1right += 1while window[r] > 1:l = s[left]window[l] -= 1left += 1# 没有重复的才计算最大长度cur_len = right - leftlongest_len = max(cur_len, longest_len)return longest_len

4、字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。
示例 1：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

class Solution:def checkInclusion(self, s1: str, s2: str) -> bool:left = right = 0needs, window = {}, {}flag = Falsematch = 0for v in s1: needs[v] = needs.get(v, 0) + 1while right < len(s2):r = s2[right]if needs.get(r):window[r] = window.get(r, 0) + 1if window[r] == needs[r]: match += 1right += 1if (right - left) == len(s1):if match == len(needs):flag = Truebreakl = s2[left]if needs.get(l):if window[l] == needs[l]: match -= 1window[l] -= 1left += 1return flag