LeetCode | 滑动窗口的原理及真题解析

滑动窗口是一种双指针技术，用于处理数组或字符串中连续区间的问题。通过一个“窗口”在数组上从左到右滑动，寻找满足某个条件的子区间。

动态维护一个“窗口”，只包含一段区间的数据，在保持区间性质的同时：

• 右指针右移扩大窗口

• 左指针右移缩小窗口

• 最终得到一个最优解（最大/最小长度，出现次数等）

1.滑动窗口的常见形式

类型	描述	示例题目
固定长度窗口	窗口大小固定，左右指针同步滑动	Leetcode 239
可变长度窗口	窗口根据条件动态调整左边界	Leetcode 3 / 76
滑动+统计/哈希频率	统计窗口内字符频率或特征	Leetcode 567 / 438

2.如何判断 Leetcode 题目是否适合用滑动窗口？

常见关键词：

• “连续子串 / 子数组”

• “最长/最短长度”

• “包含多少种字符”

• “所有满足条件的子串”

• “在字符串中查找模式/异位词”

典型特征：

特征	是否适合滑动窗口
子区间必须是连续的	✅
问题与字符/元素频率有关	✅
多次查询子区间信息	✅
涉及所有子集/组合/不连续位置	❌（更适合回溯或位运算）

Leetcode 高频滑动窗口题目

题号	题目	类型
3	无重复字符的最长子串	可变长度窗口
76	最小覆盖子串	可变长度 + 字符频率
567	字符串的排列	固定长度 + 频率对比
438	找到字符串中所有字母异位词	固定长度 + 滑动频率
239	滑动窗口最大值	固定窗口 + 单调队列
209	长度最小的子数组	可变窗口 + 滑动加和
30	串联所有单词的子串	固定窗口 + 哈希

【Leetcode 76】最小覆盖子串 Minimum Window Substring

 给你字符串 s 和字符串 t，返回包含 t 所有字符的最小子串。如果不存在，返回空字符串。

#最优解：滑动窗口 + 字符计数
from collections import Counterdef minWindow(s: str, t: str) -> str:if not s or not t:return ""need = Counter(t)window = {}have = 0need_count = len(need)left = 0res = ""res_len = float("inf")for right, c in enumerate(s):window[c] = window.get(c, 0) + 1if c in need and window[c] == need[c]:have += 1while have == need_count:# 更新最小窗口if (right - left + 1) < res_len:res = s[left:right+1]res_len = right - left + 1# 移动左边界，缩小窗口window[s[left]] -= 1if s[left] in need and window[s[left]] < need[s[left]]:have -= 1left += 1return res#时间复杂度：O(|S| + |T|)
#空间复杂度：O(|T|)

【Leetcode 639】Sliding Window Maximum

 给你一个整数数组 nums 和一个整数 k，在所有大小为 k 的滑动窗口中找出最大值。

# 最优解：单调队列
from collections import dequedef maxSlidingWindow(nums, k):q = deque()res = []for i in range(len(nums)):# 移除窗口外的索引if q and q[0] <= i - k:q.popleft()# 维持单调递减栈：移除小于当前值的元素while q and nums[q[-1]] < nums[i]:q.pop()q.append(i)# 从第 k 个位置开始记录结果if i >= k - 1:res.append(nums[q[0]])return res#时间复杂度：O(n)
#空间复杂度：O(k)（最多存 k 个索引）

想要了解更多内容，可在VX小程序搜索🔍AI Pulse,获取更多最新内容。