Python 滑动窗口算法：从入门到实战，高效解决数组与字符串问题299

在编程面试和日常开发中，我们经常需要处理各种序列数据，例如数组（列表）和字符串。当面对需要查找特定子序列、计算子序列属性或者优化子序列相关操作的问题时，朴素的暴力法（例如 O(N^2) 或 O(N^3)）往往效率低下，难以满足性能要求。此时，一种名为“滑动窗口”（Sliding Window）的算法技巧便能大放异彩，它以其精妙的指针移动策略，将许多看似复杂的 O(N^2) 问题优化到 O(N) 的线性时间复杂度。

本文将作为一份全面的指南，带你深入了解 Python 中滑动窗口算法的原理、实现方式、常见应用场景以及高级技巧。无论你是算法初学者还是经验丰富的开发者，都能从中获得宝贵的知识，提升解决序列问题的能力。

一、滑动窗口算法简介

滑动窗口算法是一种双指针技术，它通过维护一个动态的“窗口”来遍历序列。这个窗口通常由两个指针（`left` 和 `right` 或 `start` 和 `end`）界定，代表当前正在处理的子序列范围。随着 `right` 指针向右移动以扩展窗口，`left` 指针也根据特定条件向右移动以收缩窗口，从而保证窗口内的元素始终满足某些约束条件。

1. 为什么需要滑动窗口？

考虑一个经典问题：给定一个数组，找出所有长度为 `k` 的子数组的和。

nums = [1, 2, 3, 4, 5, 6]
k = 3
# 暴力解法 (O(N*K) 或 O(N^2))
sums = []
for i in range(len(nums) - k + 1):
current_sum = 0
for j in range(i, i + k):
current_sum += nums[j]
(current_sum)
print(sums) # 输出: [6, 9, 12, 15]

在暴力解法中，每次计算一个新的子数组的和时，我们都会重新遍历其所有 `k` 个元素。当从 `[1, 2, 3]` 移动到 `[2, 3, 4]` 时，`2` 和 `3` 被重复计算了。滑动窗口的优势在于，它避免了这种重复计算。

2. 基本思想

滑动窗口的核心思想是：当窗口从 `[i, j]` 移动到 `[i+1, j+1]` 时，新窗口的和可以通过旧窗口的和减去 `nums[i]` 并加上 `nums[j+1]` 快速得到，而不是重新计算 `[i+1, j+1]` 中的所有元素。

这就像你有一扇窗户在沿着一条街移动，每次你只关注窗户里能看到的景象。当你向前移动一步时，最左边的景色就消失了，最右边的新景色就进入视野，而中间的大部分景色保持不变。

3. 两种主要类型

固定大小滑动窗口 (Fixed-Size Sliding Window)： 窗口的大小 `k` 始终保持不变。这类问题通常是找出长度为 `k` 的子数组/子字符串的某种属性（最大和、最小平均值等）。
可变大小滑动窗口 (Variable-Size Sliding Window)： 窗口的大小会根据条件动态变化。这类问题通常是找出满足某个条件的最长/最短子数组/子字符串。

二、固定大小滑动窗口

固定大小滑动窗口是最直观的一种类型。我们通常用它来解决在给定长度 `k` 的子序列中寻找最大/最小/平均值等问题。

1. 示例：求长度为 `k` 的子数组的最大和

问题描述： 给定一个整数数组 `nums` 和一个整数 `k`，找出和最大的长度为 `k` 的连续子数组，并返回其最大和。

思路：

初始化 `left = 0`，`right = 0`。
计算第一个大小为 `k` 的窗口的和。
从 `k` 开始，`right` 指针每次向右移动一步：

将 `nums[right]` 加入窗口和。
将 `nums[left]` 从窗口和中移除。
`left` 指针也向右移动一步。
在每次滑动后，更新最大和。

Python 代码实现：
def max_sum_subarray_fixed(nums: list[int], k: int) -> int:
"""
找出长度为 k 的子数组的最大和（固定大小滑动窗口）。
:param nums: 整数数组
:param k: 子数组长度
:return: 最大和
"""
if not nums or k len(nums):
# 边界条件处理
if k == 0: return 0 # 长度为0的子数组和为0
return float('-inf') # 无效输入，返回负无穷
current_window_sum = 0
# 1. 计算第一个窗口的和
for i in range(k):
current_window_sum += nums[i]

max_sum = current_window_sum

# 2. 滑动窗口
# right 指针从 k 开始，直到数组末尾
for right in range(k, len(nums)):
# 窗口向右滑动一步
# 移除最左边的元素
current_window_sum -= nums[right - k]
# 添加最右边的新元素
current_window_sum += nums[right]

# 更新最大和
max_sum = max(max_sum, current_window_sum)

return max_sum
# 示例测试
nums1 = [1, 2, 3, 4, 5, 6]
k1 = 3
print(f"数组 {nums1}, k={k1} 的最大子数组和: {max_sum_subarray_fixed(nums1, k1)}") # 输出: 15 ([4, 5, 6])
nums2 = [-1, -2, -3, -4, -5]
k2 = 2
print(f"数组 {nums2}, k={k2} 的最大子数组和: {max_sum_subarray_fixed(nums2, k2)}") # 输出: -3 ([-1, -2])
nums3 = [7, 1, 8, 5, 2, 9, 3]
k3 = 4
print(f"数组 {nums3}, k={k3} 的最大子数组和: {max_sum_subarray_fixed(nums3, k3)}") # 输出: 24 ([8, 5, 2, 9])

复杂度分析：

时间复杂度： O(N)。`right` 指针遍历数组一次，每次操作都是常数时间。
空间复杂度： O(1)。只使用了几个变量来存储和和最大值。

相较于暴力法的 O(N*K) 或 O(N^2)，这是一个显著的优化。

三、可变大小滑动窗口

可变大小滑动窗口是滑动窗口算法更强大和灵活的应用形式。它没有预设的窗口大小，而是根据窗口内元素是否满足特定条件来动态调整窗口边界。

1. 核心流程

可变大小滑动窗口通常遵循以下模式：

初始化 `left = 0`，`current_condition_metric = 0` (例如当前和、字符计数等)，`result = initial_value` (例如最大长度 0，最小长度 infinity)。
`right` 指针向右遍历序列，每次将 `nums[right]` （或 `s[right]`）添加到窗口中，并更新 `current_condition_metric`。
当 `current_condition_metric` 满足某个条件时（例如 `current_sum >= target` 或窗口内有重复字符），开始收缩窗口：

更新 `result`（例如 `max_length = max(max_length, right - left + 1)` 或 `min_length = min(min_length, right - left + 1)`）。
将 `nums[left]` （或 `s[left]`）从窗口中移除，并更新 `current_condition_metric`。
`left` 指针向右移动一步。


重复步骤 2 和 3，直到 `right` 指针遍历完整个序列。

2. 示例：最长无重复字符的子串

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

思路：

使用一个集合（`char_set`）来存储当前窗口中的字符，判断是否有重复。
`right` 指针向右扩展窗口。如果 `s[right]` 不在 `char_set` 中，就将其加入集合，并更新当前最长子串的长度。
如果 `s[right]` 已经在 `char_set` 中（出现重复），则 `left` 指针开始向右收缩窗口，同时从 `char_set` 中移除 `s[left]`，直到窗口中不再有重复字符。
重复以上步骤直到 `right` 遍历完字符串。

Python 代码实现：
def length_of_longest_substring(s: str) -> int:
"""
找出最长无重复字符的子串的长度（可变大小滑动窗口）。
:param s: 输入字符串
:return: 最长无重复字符子串的长度
"""
if not s:
return 0
char_set = set() # 用于存储当前窗口中的字符
left = 0
max_length = 0
for right in range(len(s)):
# 扩展窗口
# 如果当前字符已经在集合中，说明有重复，需要收缩窗口
while s[right] in char_set:
(s[left]) # 移除最左边的字符
left += 1 # 左指针右移

# 当前字符不在集合中，可以加入窗口
(s[right])
# 更新最长长度
max_length = max(max_length, right - left + 1)

return max_length
# 示例测试
print(f"'abcabcbb' 的最长无重复字符子串长度: {length_of_longest_substring('abcabcbb')}") # 输出: 3 ('abc')
print(f"'bbbbb' 的最长无重复字符子串长度: {length_of_longest_substring('bbbbb')}") # 输出: 1 ('b')
print(f"'pwwkew' 的最长无重复字符子串长度: {length_of_longest_substring('pwwkew')}") # 输出: 3 ('wke')
print(f"'' 的最长无重复字符子串长度: {length_of_longest_substring('')}") # 输出: 0
print(f"' ' 的最长无重复字符子串长度: {length_of_longest_substring(' ')}") # 输出: 1
print(f"'dvdf' 的最长无重复字符子串长度: {length_of_longest_substring('dvdf')}") # 输出: 3 ('vdf')

复杂度分析：

时间复杂度： O(N)。`right` 指针遍历数组一次，`left` 指针也最多遍历一次。每个字符最多被添加和移除一次。
空间复杂度： O(字符集大小)，在 ASCII 码表的情况下是 O(128)，或者说是 O(1)。在更通用的 Unicode 字符集中，可能是 O(N) 的最坏情况（所有字符都不重复）。

3. 示例：长度最小的子数组

问题描述： 给定一个正整数数组 `nums` 和一个正整数 `target`。找出 `nums` 中和大于或等于 `target` 的长度最小的连续子数组，并返回其长度。如果不存在，则返回 0。

思路：

使用 `current_sum` 记录当前窗口的和。
`right` 指针向右扩展窗口，将 `nums[right]` 加入 `current_sum`。
当 `current_sum` 大于或等于 `target` 时，表示找到了一个符合条件的子数组。此时，尝试收缩 `left` 指针以寻找更短的子数组：

更新 `min_length = min(min_length, right - left + 1)`。
从 `current_sum` 中减去 `nums[left]`。
`left` 指针向右移动。
重复此过程直到 `current_sum < target`。

Python 代码实现：
def min_subarray_len(target: int, nums: list[int]) -> int:
"""
找出和大于或等于 target 的长度最小的连续子数组（可变大小滑动窗口）。
:param target: 目标和
:param nums: 整数数组
:return: 最小子数组长度，如果不存在则返回 0
"""
if not nums:
return 0
left = 0
current_sum = 0
min_length = float('inf') # 初始化为无穷大
for right in range(len(nums)):
# 扩展窗口
current_sum += nums[right]
# 满足条件时，尝试收缩窗口
while current_sum >= target:
# 更新最小长度
min_length = min(min_length, right - left + 1)

# 收缩窗口
current_sum -= nums[left]
left += 1

# 如果 min_length 仍然是无穷大，说明没有找到符合条件的子数组
return min_length if min_length != float('inf') else 0
# 示例测试
print(f"target=7, nums=[2,3,1,2,4,3] 的最小子数组长度: {min_subarray_len(7, [2,3,1,2,4,3])}") # 输出: 2 ([4,3] 或 [2,4,3] 都可以，但最小长度是2)
print(f"target=4, nums=[1,4,4] 的最小子数组长度: {min_subarray_len(4, [1,4,4])}") # 输出: 1 ([4])
print(f"target=11, nums=[1,1,1,1,1,1,1,1] 的最小子数组长度: {min_subarray_len(11, [1,1,1,1,1,1,1,1])}") # 输出: 0
print(f"target=15, nums=[1,2,3,4,5] 的最小子数组长度: {min_subarray_len(15, [1,2,3,4,5])}") # 输出: 5 ([1,2,3,4,5])

复杂度分析：

时间复杂度： O(N)。`right` 和 `left` 指针都最多遍历数组一次。
空间复杂度： O(1)。

四、滑动窗口的变种与技巧

滑动窗口算法在解决实际问题时，可以结合其他数据结构和技巧，以应对更复杂的需求。

1. 使用哈希表（字典）计数

当处理字符串问题，需要追踪窗口内字符的频率或特定字符出现的次数时，哈希表（Python 中的 `dict`）非常有用。例如，在查找异位词、最小覆盖子串等问题中，哈希表能高效地进行字符频率的增减和比较。
# 示例：查找字符串中所有字母异位词
# def find_anagrams(s: str, p: str) -> list[int]:
# ... (实现中使用字典记录p中字符频率，滑动窗口检查s中子串的频率)

2. 使用集合（Set）判断唯一性

如前文“最长无重复字符的子串”示例所示，当仅需要判断窗口内元素是否唯一时，`set` 提供了 O(1) 的平均时间复杂度来完成插入、删除和查找操作。

3. 双端队列（Deque）处理最大/最小值问题

对于“滑动窗口最大值”或“滑动窗口最小值”这类问题，标准滑动窗口需要 O(K) 查找窗口内极值，总复杂度 O(N*K)。如果使用双端队列（``），可以实现 O(N) 的时间复杂度。双端队列在这里充当一个“单调队列”，维护窗口内元素的有序子集。
from collections import deque
def max_sliding_window(nums: list[int], k: int) -> list[int]:
"""
找出滑动窗口的最大值（使用双端队列）。
:param nums: 整数数组
:param k: 窗口大小
:return: 包含每个窗口最大值的列表
"""
if not nums or k == 0:
return []
if k == 1:
return nums
deque_ = deque() # 存储元素的索引
results = []
for i in range(len(nums)):
# 移除队列中所有小于当前元素的索引
# 这些元素不可能成为后续窗口的最大值
while deque_ and nums[deque_[-1]] = k-1），队列头部的元素就是当前窗口的最大值
if i >= k - 1:
(nums[deque_[0]])
return results
# 示例测试
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(f"数组 {nums}, k={k} 的滑动窗口最大值: {max_sliding_window(nums, k)}") # 输出: [3, 3, 5, 5, 6, 7]

4. 模板化思考

当你遇到一个序列问题，感觉可能可以用滑动窗口解决时，可以尝试以下模板化步骤：

定义窗口： 确定 `left` 和 `right` 指针。
扩展窗口： 每次 `right` 指针向右移动，将 `nums[right]` 加入窗口，并更新窗口状态（`current_sum`、`char_count` 等）。
判断条件： 检查当前窗口是否满足问题要求的条件。
收缩窗口： 如果条件满足（或不满足，取决于问题），则 `left` 指针向右移动，将 `nums[left]` 移出窗口，并更新窗口状态，直到条件不再满足（或再次满足）。
更新结果： 在每次窗口扩展或收缩后，根据问题要求更新最终结果（例如 `max_length`、`min_length`、`count` 等）。

五、适用场景与总结

滑动窗口算法非常适合解决以下类型的问题：

在数组或字符串中查找满足特定条件的最长/最短子数组或子字符串。
计算长度为 `k` 的所有子数组或子字符串的统计量（和、平均值、最大值、最小值等）。
查找子数组或子字符串的计数，例如有多少个子数组满足某个和的条件。
优化暴力枚举所有子数组/子字符串的 O(N^2) 或 O(N^3) 方案。

滑动窗口算法是双指针技术的一种巧妙应用，它通过维护一个动态窗口并避免重复计算，大大提高了处理序列问题的效率。理解其固定大小和可变大小两种基本形式，并掌握结合哈希表、集合、双端队列等数据结构的技巧，将使你在解决各种算法挑战时游刃有余。

通过本文的学习和代码实践，相信你已经对 Python 滑动窗口算法有了深入的理解。在未来的算法学习和实践中，尝试识别和应用这一高效模式，你的代码将更加优化和强大！

2025-10-29

---

上一篇：Python列表与数组转换为字符串：方法、场景与最佳实践

下一篇：Python文件更名：从基础到高级的自动化指南