固定窗口与滑动窗口
1. 简介
固定窗口
- 定义：窗口包含的元素个数（长度）始终保持不变。
- 特点：移动时按固定步长整体平移，不会增减窗口内元素数量。
- 适用场景：固定范围的统计或计算，比如固定时间窗口的接口限流、长度为 k 的子数组求和。
可变窗口
- 定义：窗口长度可根据需求动态扩大或缩小，沿数据序列单向滑动。
- 特点：通过调整左右边界控制窗口大小，避免重复计算，时间复杂度更低。
- 适用场景：可变范围的序列问题，比如最长无重复子串、最小覆盖子串、满足条件的子数组个数。
核心区别
- 窗口大小：固定窗口始终不变，滑动窗口可动态调整。
- 移动逻辑：固定窗口是整体平移，滑动窗口是 “边界伸缩 + 滑动” 结合。
- 效率侧重：固定窗口实现简单，滑动窗口在可变范围问题中更高效。
2. 案例与实现
1. 固定窗口
问题：给定数组 nums 和整数 k，求所有长度为 k 的连续子数组的最大和。
思路：
- 先计算第一个窗口（前 k 个元素）的和；
- 滑动窗口时，每次减去窗口左侧离开的元素，加上右侧进入的元素，避免重复计算；
- 实时更新最大和。
def max_sum_fixed_window(nums, k):
n = len(nums)
if n < k or k <= 0: # 边界条件
return 0
# 初始化第一个窗口的和
current_sum = sum(nums[:k])
max_sum = current_sum
# 滑动窗口（从第 k 个元素开始）
for i in range(k, n):
# 移除左侧元素，加入右侧新元素
current_sum = current_sum - nums[i - k] + nums[i]
max_sum = max(max_sum, current_sum)
return max_sum
# 测试
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(max_sum_fixed_window(nums, k)) # 输出：16（对应子数组 [3,6,7]）
2. 可变窗口
问题：给定字符串 s，找出其中不含有重复字符的最长子串的长度。
思路：
- 用左右指针
left、right维护窗口，right向右扩展； - 用哈希表
char_index记录字符最后出现的位置； - 若
right指向的字符已在窗口中（即char_index[char] >= left），则将left移到该字符上次出现位置的右侧（保证窗口内无重复）； - 实时更新最长子串长度。
def length_of_longest_substring(s):
char_index = {} # 记录字符最后出现的索引
max_len = 0
left = 0 # 窗口左边界
for right, char in enumerate(s):
# 若字符已在当前窗口内，移动左边界到重复位置右侧
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1
# 更新字符最新位置和最大长度
char_index[char] = right
max_len = max(max_len, right - left + 1)
return max_len
# 测试
s = "abcabcbb"
print(length_of_longest_substring(s)) # 输出：3（对应 "abc"）
发表评论