当前位置：首页 > news >正文

【leetcode】滑动窗口刷题总结

news 来源：原创 2025/7/6 14:07:03

滑动窗口算法技巧主要用来解决子数组问题，比如让你寻找符合某个条件的最长/最短子数组或者子串。对于某些题目，并不需要穷举所有子串，就能找到题目想要的答案。滑动窗口就是这种场景下的一套算法模板，帮你对穷举过程进行剪枝优化，将求解子串复杂度由O(N^2)->O(N)

滑动窗口-定长滑动窗口

定长滑窗三步曲：入-更新-出

入（扩大窗口）：下标为 i 的元素进入窗口，更新相关统计量
更新：更新答案，一般是更新最大值/最小值
出（更新窗口）：下标为 i−k+1 的元素离开窗口，更新相关统计量

LeetCode1456题定长子串中元音的最大数目

class Solution:def maxVowels(self, s: str, k: int) -> int:res = num = 0for i in range(len(s)):# 入if s[i] in 'aeiou':num += 1# 长度不足，继续向前if i < k - 1:continue# 更新res = max(res, num)# 出if s[i - k + 1] in 'aeiou':num -= 1return res

LeetCode438题找到字符串中所有字母异位词

class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:res = []need_dict = dict()for s_ in p:need_dict[s_] = need_dict.get(s_, 0) + 1satisfy_num = 0for right in range(len(s)):# 入if s[right] in need_dict:need_dict[s[right]] -= 1if need_dict[s[right]] == 0:satisfy_num += 1if right < len(p) - 1:continue# 更新if satisfy_num == len(need_dict):res.append(right - len(p) + 1)# 出if s[right - len(p) + 1] in need_dict:need_dict[s[right - len(p) + 1]] += 1if need_dict[s[right - len(p) + 1]] == 1:satisfy_num -= 1return res

LeetCode30题串联所有单词的子串

“找到字符串中所有字母异位词”的升级版，将“字母异位”升级为“单词异位”。首先需要将s划分为单词组，每个单词的大小均为n，这样的划分方法有n种，即先删去前i （i=0∼n−1）个字母后，将剩下的字母进行划分，如果末尾有不到 n 个字母也删去。对这n种划分得到的单词数组分别使用滑动窗口对words进行类似于「字母异位词」的搜寻

class Solution:def findSubstring(self, s: str, words: List[str]) -> List[int]:res = []m, n = len(words), len(words[0])for i in range(n):# 初始化变量need_dict = dict()satisfy_num = 0for w in words:need_dict[w] = need_dict.get(w, 0) + 1# 滑动窗口for right in range(i, len(s)):# 入if (right - i + 1) % n == 0:s_ = s[right - n + 1: right + 1]if s_ in need_dict:need_dict[s_] -= 1if need_dict[s_] == 0:satisfy_num += 1if right - i + 1 < m * n:continue# 更新if satisfy_num == len(need_dict):res.append(right - m * n + 1)# 出if (right - i + 1) % n == 0:s_ = s[right - m * n + 1: right - n * m + n + 1]if s_ in need_dict:need_dict[s_] += 1if need_dict[s_] == 1:satisfy_num -= 1return res

滑动窗口-不定长滑动窗口-求最长子数组/子串

LeetCode3题无重复字符的最长子串

窗口就是无重复字符的连续子串
窗口的起始位置如何移动：如果当前窗口不满足条件，窗口起始位置就要向前移动
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:res = 0left = 0visited = dict()for right in range(len(s)):# 入visited[s[right]] = visited.get(s[right], 0) + 1# 出：当不满足条件时，需要持续向右移动left指针while visited[s[right]] > 1:visited[s[left]] -= 1left += 1# 更新：统计加入s[right]时满足条件的子串长度res = max(res, right - left + 1)return res

LeetCode904题水果成篮

class Solution:def totalFruit(self, fruits: List[int]) -> int:res = 0left = 0window_fruits = dict()window_num = 0for right in range(len(fruits)):# 入window_fruits[fruits[right]] = window_fruits.get(fruits[right], 0) + 1window_num += 1# 出while len(window_fruits) >= 3:window_fruits[fruits[left]] -= 1if window_fruits[fruits[left]] == 0:del window_fruits[fruits[left]]left += 1window_num -= 1# 更新res = max(res, window_num)return res

LeetCode395题至少有K个字符的最长子串

我们枚举最长子串中的字符种类数目，它最小为 1，最大为26。对于给定的字符种类数量，我们维护滑动窗口的左右边界、滑动窗口内部每个字符出现的次数，以及滑动窗口内的字符种类数。当种类数超过设定时，我们不断地右移左边界，并对应地更新其他变量，并记录下符合条件的最长子串

class Solution:def longestSubstring(self, s: str, k: int) -> int:res = 0for max_char_num in range(1, 27):left = 0window_count = dict()satisfy_num = 0for right in range(len(s)):# 入window_count[s[right]] = window_count.get(s[right], 0) + 1if window_count[s[right]] == k:satisfy_num += 1# 出while len(window_count) > max_char_num:window_count[s[left]] -= 1if window_count[s[left]] == k - 1:satisfy_num -= 1if window_count[s[left]] == 0:del window_count[s[left]]left += 1# 更新if satisfy_num == len(window_count):res = max(res, right - left + 1)return res

滑动窗口-不定长滑动窗口-求最短子数组/子串

LeetCode76题最小覆盖子串

class Solution:def minWindow(self, s: str, t: str) -> str:res = ''# 记录需要覆盖的字母数量need = dict()for i in t:need[i] = need.get(i, 0) + 1# 记录覆盖的字母数量cover = 0# 初始化左边界left = 0for right in range(len(s)):# 入if s[right] in need:need[s[right]] -= 1if need[s[right]] == 0:cover += 1# 出：当满足条件时，记录覆盖字串，同时开始将左侧指针右移while cover == len(need):# 更新结果if right - left + 1 < len(res) or len(res) == 0:res = s[left: right + 1]if s[left] in need:need[s[left]] += 1if need[s[left]] == 1:cover -= 1left += 1return res

LeetCode209题长度最小的子数组

窗口就是满足和>=target的连续子数组
窗口的起始位置如何移动：如果当前窗口的值>=target，窗口就要向右移动
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:res = len(nums) + 1window_sum = 0left = 0for right in range(len(nums)):# 入window_sum += nums[right]# 出while window_sum >= target:# 更新res = min(res, right - left + 1)window_sum -= nums[left]left += 1if res == len(nums) + 1:return 0else:return res

LeetCode632题最小区间

排序 + 滑动窗口：把所有元素都合在一起排序，可以得到（元素值，所属列表编号）组成的数组，合法区间等价于排序后的一个连续子数组，满足列表编号0～k-1都在这个子数组中。由于子数组越长，越能包含所有编号，有单调性，可以用滑动窗口解决

class Solution:def smallestRange(self, nums: List[List[int]]) -> List[int]:sorted_nums = sorted([(x, i) for i, arr in enumerate(nums) for x in arr])cover_count = dict()res = [-10**5, 10**5]left = 0for right in range(len(sorted_nums)):# 入cover_count[sorted_nums[right][1]] = cover_count.get(sorted_nums[right][1], 0) + 1while len(cover_count) == len(nums):# 更新l, r = sorted_nums[left][0], sorted_nums[right][0]if r - l < res[1] - res[0] or (r - l == res[1] - res[0] and l < res[0]):res = [l, r]# 出cover_count[sorted_nums[left][1]] -= 1if cover_count[sorted_nums[left][1]] == 0:del cover_count[sorted_nums[left][1]]left += 1return res

滑动窗口-不定长滑动窗口-求子数组个数

LeetCode1358题包含所有三种字符的子字符串数目

越长越合法：平移左指针，不断调整右指针位置直到符合条件，右指针右侧都是符合条件的子数组

class Solution:def numberOfSubstrings(self, s: str) -> int:res = 0right = 0window_count = dict()for left in range(len(s)):# 入while len(window_count) < 3 and right < len(s):window_count[s[right]] = window_count.get(s[right], 0) + 1right += 1# 更新if len(window_count) == 3:res += len(s) - right + 1# 出window_count[s[left]] -= 1if window_count[s[left]] == 0:del window_count[s[left]]return res

LeetCode713题乘积小于K的子数组

越短越合法：平移右指针，不断调整左指针位置直到符合条件，左指针右侧都是符合条件的子数组

class Solution:def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:res = 0window_res = 1left = 0for right in range(len(nums)):# 入window_res *= nums[right]# 出while window_res >= k and left <= right:window_res /= nums[left]left += 1# 更新res += right - left + 1return res

LeetCode930题和相同的二元子数组

要计算有多少个元素和恰好等于k的子数组，可以把问题变成：

计算有多少个元素和<=k的子数组
计算有多少个元素和<=k-1的子数组

然后将两个值相减，就是答案

class Solution:def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:return self.sliding_window(nums, goal) - self.sliding_window(nums, goal - 1)def sliding_window(self, nums, k):# 和<=k的子数组个数res = 0window_sum = 0left = 0for right in range(len(nums)):window_sum += nums[right]while window_sum > k and left <= right:window_sum -= nums[left]left += 1res += right - left + 1return res

滑动窗口-定长滑动窗口

LeetCode1456题 定长子串中元音的最大数目

LeetCode438题 找到字符串中所有字母异位词

LeetCode30题 串联所有单词的子串

滑动窗口-不定长滑动窗口-求最长子数组/子串

LeetCode3题 无重复字符的最长子串

LeetCode904题 水果成篮

LeetCode395题 至少有K个字符的最长子串

滑动窗口-不定长滑动窗口-求最短子数组/子串

LeetCode76题 最小覆盖子串

LeetCode209题 长度最小的子数组

LeetCode632题 最小区间