admin
LeetCode 热题 | 滑动窗口
11/9/2025
滑动窗口
一、什么是滑动窗口？
滑动窗口是一种基于双指针的算法技巧。它通过维护一个窗口（通常是数组或字符串中的一个连续子区间），通过移动窗口的起始和结束指针来高效地解决问题。
其核心思想是：通过已经获取的信息，避免重复计算，从而将嵌套循环问题转化为单次遍历问题，降低时间复杂度。
二、核心思想与为什么有效
想象一下，你在用一个固定大小的框从左到右扫描一个序列。每次框移动时，你只关心框内的内容。滑动窗口的精妙之处在于：
“滑动”：窗口不是静态的，而是从左向右移动。
“窗口”：我们只关注当前窗口内的元素，窗口外的元素可以忽略。
“避免重复计算”：当窗口向右滑动一位时，我们不是重新计算整个新窗口的值，而是根据旧窗口的结果，减去离开窗口的元素的影响，加上新进入窗口的元素的影响。这极大地提高了效率。
三、适用场景/题型特征
当你看到题目具有以下特征时，就应该考虑滑动窗口：
数据结构是数组或字符串。
求解的目标与一段连续子序列（子数组/子字符串）相关。
例如：“最长”、“最短”、“连续”、“子串”、“子数组”等关键词。
存在某种约束条件。
例如：求和最大/最小、不含重复字符、包含某些特定元素等。
四、滑动窗口的两种主要类型
滑动窗口主要分为两类：固定大小窗口和可变大小窗口。
1. 固定大小窗口
窗口的大小是预先确定的，在滑动过程中保持不变。
解题思路：
先初始化第一个窗口（从下标0到k-1），并计算出它的值（如求和）。
然后从下标k开始遍历，每次向右移动一位。
每次移动时，从当前和中减去nums[i - k]（刚离开窗口的左边界元素），并加上nums[i]（新进入窗口的右边界元素）。
根据题目要求，更新最终结果（如最大值或最小值）。
经典例题：
子数组最大平均数 I (LeetCode 643)：给定一个整数数组，找出平均数最大且长度为 k 的连续子数组。
定长子串中元音的最大数目 (LeetCode 1456)
2. 可变大小窗口（更常见、更难）
窗口的大小是不固定的，它根据题目条件动态地扩大和缩小。这是考察的重点。
解题思路（双指针模板）：
初始化：两个指针 left 和 right，通常都从0开始。用一个数据结构（如哈希表window）来记录当前窗口内的状态（如字符频率）。
扩大窗口（寻找可行解）：移动 right 指针，扩大窗口，并更新窗口状态window，直到窗口满足了题目的约束条件。
收缩窗口（优化可行解）：一旦窗口满足条件，可能就开始移动 left 指针，收缩窗口。在收缩的同时，更新窗口状态，并检查窗口是否依然满足条件。每次收缩时，都可以更新最终结果（因为此时窗口是满足条件的）。
循环：重复步骤2和3，直到 right 指针到达序列的尽头。
关键点： 需要明确：
何时扩大窗口（右指针移动）？
何时收缩窗口（左指针移动）？
何时更新最终结果？
经典例题：
无重复字符的最长子串 (LeetCode 3)：窗口内不能有重复字符。
最小覆盖子串 (LeetCode 76)：窗口需要包含目标字符串的所有字符。
字符串的排列 (LeetCode 567)：窗口需要是目标字符串的一个排列。
找到字符串中所有字母异位词 (LeetCode 438)
五、通用解题步骤
定义窗口和状态：确定需要用什么数据结构来记录窗口的状态（常用HashMap或数组来记录频率）。
初始化指针和变量：left = 0, right = 0，以及记录最终结果的变量（如maxLen, minLen）。
开始遍历（外循环）：通常以 right 指针遍历整个序列作为外循环。
更新右边界和窗口状态：将 right 指向的元素加入窗口，更新状态。
内循环收缩左边界：while（当前窗口违反或满足某种条件，这取决于题目）{
更新最终结果（如果需要）。
将 left 指向的元素移出窗口，更新状态。
left++。
}
更新最终结果：在某些情况下，需要在内循环外部更新结果。
返回结果。
3. 无重复字符的最长子串
已解答 中等
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。（子字符串 是字符串中连续的 非空 字符序列。）
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
解题代码：
我的思路相当于创建了一个新的列表当做滑动窗口，这样做的好处是：当遇见重复值时，可以直接使用 List.index() 函数来进行下一个窗口左边界的确定，然后继续更新窗口右边界即可。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# s = list(s) 不需要转化成列表，字符串一样可以使用s[i]
l= 0
num = []
for i in range(len(s)):
if s[i] in num:
l = max(len(num),l)
num = num[num.index(s[i])+1:]
num.append(s[i])
else:
num.append(s[i])
l = max(len(num),l)
return l
LeetCode官方的解法是创建左右指针，而且左指针的操作是依次向前+1，个人认为这样不太好，如果右指针确定的重复数在窗口的中间，其实每次左指针只+1仍要增加一次判断，虽然判断后的结果是左指针继续+1。而上面使用 List 的方法，相当于直接确定了左指针下一次具体位置，也就是你找到的那个重复数在原窗口的下一个地址 num = num[num.index(s[i])+1:] 。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 哈希集合，记录每个字符是否出现过
occ = set()
n = len(s)
# 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
rk, ans = -1, 0
for i in range(n):
if i != 0:
# 左指针向右移动一格，移除一个字符
occ.remove(s[i - 1])
while rk + 1 < n and s[rk + 1] not in occ:
# 不断地移动右指针
occ.add(s[rk + 1])
rk += 1
# 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = max(ans, rk - i + 1)
return ans
# 作者：力扣官方题解
# 链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/227999/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
438. 找到字符串中所有字母异位词
已解答 中等
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 （字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次）的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母
解题代码：
这道题是滑动窗口定长的情况，我的思路很简单，分别从 s 串当中截取 len(p) 长度的子串，验证子串的 set 和 p 的set是否相等即可。
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
l = len(p)
result = []
pp = sorted(p)
for i in range(len(s)-l+1):
# 这里稍微减少时间复杂度，如果首字母不在p里直接跳过即可
if s[i] not in p:
continue
si = s[i:i+l]
if sorted(si) == pp:
result.append(i)
# 这里稍微减少时间复杂度，首字母没有问题，肯定是后面的哪一项出了问题，至少能跳过一项
else:
i+=1
return result
思路基本上是一样的，我用子串的概念来解决窗口的问题，用set的方法来解决异位词判断的问题。官方给的解法，是用两个（1*26）的数组来记录每个单词出现的次数来判断异位词的，我觉着是用空间换时间，而且还比较麻烦，虽然我这个时间复杂度有点高，但是个人感觉还是更好理解，更简单。
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
s_len, p_len = len(s), len(p)
if s_len < p_len:
return []
ans = []
s_count = [0] * 26
p_count = [0] * 26
for i in range(p_len):
s_count[ord(s[i]) - 97] += 1
p_count[ord(p[i]) - 97] += 1
if s_count == p_count:
ans.append(0)
for i in range(s_len - p_len):
s_count[ord(s[i]) - 97] -= 1
s_count[ord(s[i + p_len]) - 97] += 1
if s_count == p_count:
ans.append(i + 1)
return ans
# 作者：力扣官方题解
# 链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string/solutions/1123971/zhao-dao-zi-fu-chuan-zhong-suo-you-zi-mu-xzin/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。