数组的滑动窗口算法
Posted on Wed, 26 Nov 2025 09:51:54 +0800 by LiangMingJian
概述
滑动窗口算法，Sliding Window，是一种在数组上维护一个固定或可变长度窗口，然后通过滑动和缩放窗口，动态维护区间内的数据的算法。
滑动窗口算法本质上是快慢指针算法的一种特殊应用，可以简单的将这个算法功能理解为：使用两个指针维护一个区间，通过动态调整区间范围来满足题目要求，得出结果。
滑动窗口算法常用于查找数组中满足特定条件子数组的问题。
算法解析
如下图所示，可以看见，滑动窗口算法通过两个指针 left 和 right 构造了一个活动区间，这个活动区间可以进行滑动（通常是向右滑动），也可以进行缩放（左指针向右缩小窗口，右指针向右放大窗口），通过这样的区间调整来满足用户需求。
滑动窗口算法的应用分为固定长度窗口和可变长度窗口两种，不同的应用在实现时有不同的处理方式。
固定长度窗口
步骤分析
固定长度滑动窗口算法的实现步骤大致分为以下五步：
- 定义两个指针
left和right，默认都指向数组起始位置（left=0, right=0），创建一个数组window = [left, right]来表示当前窗口。 - 构造一个循环，不断右移右指针
right，扩大窗口范围，并将新元素加入窗口数组window中。 - 当窗口数组
window的长度等于用户需求长度时，判断窗口数组window内的元素是否满足用户需求。在完成判断后，将左指针left右移，缩小窗口长度。 - 每次迭代，右指针
right保持右移，确保窗口滑动同时窗口的长度不变。 - 重复上述步骤，直到右指针
right到达数组末尾，结束循环。
从上述步骤不难看出，固定长度滑动窗口算法的特点在于设置的窗口数组 window 长度在循环中是不变的，这种特征能用来处理统计或查找长度固定的子数组问题。
示例：求长度为 3 且元素和为 10 的子数组
给定数组 [5,2,5,3,7,2,1,1,2,7]，求这个数组中所有长度为 3，元素和为 10 的子数组，并返回对应子数组列表。
from typing import List
def numOfSum(nums: List[int], window_size: int, target: int) -> List[list]:
# 构建左右指针
left, right = 0, 0
# 构建窗户
window = []
# 窗户元素和
window_sum = 0
# 结果数组
result = []
# 构建循环，结束条件为右指针 right 到达数组末尾
while right < len(nums):
# 将右指针所指示元素加入窗口
window.append(nums[right])
# 计算元素和
window_sum += nums[right]
# 当窗口长度达到要求尺寸 size 时，判断是否满足条件
if right - left + 1 == window_size:
# 判断当前窗口的和等不等于目标值
if window_sum == target:
result.append(window.copy())
# 减去不在的元素，重新计算元素和
window_sum -= nums[left]
# 移除左边界元素，准备滑动窗口
window.pop(0)
# 左边界右移，只有当长度满足时，才能缩小窗户
left += 1
# 右边界右移，扩大窗口
right += 1
return result
if __name__ == "__main__":
num = [5,2,5,3,7,2,1,1,2,7]
print(numOfSum(num, 3, 10))
# [[2, 5, 3], [7, 2, 1], [1, 2, 7]]
不定长度窗口
步骤分析
不定长度滑动窗口算法的实现步骤大致分为以下五步：
- 定义两个指针
left和right，默认都指向数组起始位置（left=0, right=0），创建一个数组window = [left, right]来表示当前窗口。 - 构造一个循环，不断右移右指针
right，扩大窗口范围，并将新元素加入窗口数组window中。 - 对窗口内容进行判断，如果不满足条件，则左指针
left右移，缩小窗口范围，直到重新满足条件。 - 每次迭代，右指针
right保持右移，确保窗口滑动。 - 重复上述步骤，直到右指针
right到达数组末尾，结束循环。
可以看出，与固定长度窗口不同，不定长度窗口不要求窗口数组的长度满足一定限制，其只关注窗口数组能否满足用户需求。因此，这种不定长度滑动窗口算法适用于查找满足条件的最长或最短区间这类问题。
示例：求给定字符串中不含重复字符的最长子串长度
给定字符串 abbccdefghjjkel，返回字符串中不含重复字符的最长子串长度。
def lengthOfLongestSubstring(string: str) -> str:
# 构建左右指针
left, right = 0, 0
# 窗口使用字典，以减少去重操作，并记录窗口内每个字符出现的次数
window = dict()
# 记录最长无重复子串的长度
res = 0
# 构造循环，结束条件为右指针 right 到达字符结尾
while right < len(string):
# 将当前字符加入窗口，并统计出现次数
if string[right] not in window:
window[string[right]] = 1
else:
window[string[right]] += 1
# 如果当前字符出现次数大于1，则说明有重复，需要收缩左边界
# 相当于，将左边界移动到当前右边界，将窗口起始位置移动到当前值
while window[string[right]] > 1:
# 将左边界字符出现次数减 1
window[string[left]] -= 1
# 移动左边界
left += 1
# 更新最长无重复子串的长度
res = max(res, right - left + 1)
# 右边界右移，扩大窗口
right += 1
return res
if __name__ == "__main__":
print(lengthOfLongestSubstring('abbcdefghjjkel'))
# 8
————————————