数据结构与算法 / 系统课时
处理定长与变长窗口差异
处理定长与变长窗口差异
滑动窗口最容易出错的地方,不是左右指针怎么写,而是什么时候收缩。本篇用一个统一判断框架区分定长窗口与变长窗口,并用两类典型题演示正确更新答案的时机。
学习目标
- 根据题意判断窗口长度是固定还是由条件动态决定
- 掌握两类窗口各自的扩张、收缩和答案更新顺序
- 避免把
if、while和更新答案的位置套错
先判断窗口受什么约束
定长窗口的核心约束是“窗口长度必须等于 k”。右端每加入一个元素,只要窗口超过 k,左端就必须同步移出一个元素,因此窗口大小始终围绕固定长度变化。
变长窗口没有固定大小,而是由某个条件控制,例如“区间和至少为 target”或“区间内不同字符不超过 k 个”。右端负责让窗口获得更多信息,左端负责在条件允许时尽量压缩。

一个实用判断是:题目如果直接给出“长度为 k 的子数组/子串”,优先考虑定长窗口;如果要求“满足条件的最短、最长区间”,通常需要变长窗口,但前提是窗口条件具有可维护的单调性。
两类窗口的代码骨架
下面把“长度为 k 的最大子数组和”和“和至少为 target 的最短子数组”放在同一个可运行示例中。第二个问题限定数组元素为正数,因为只有这样,右移右端不会让窗口和下降,左移左端也不会让窗口和上升。
def max_sum_fixed(nums, k):
if k <= 0 or k > len(nums):
return None
window_sum = sum(nums[:k])
best = window_sum
for right in range(k, len(nums)):
# 右端加入一个元素,同时移出恰好离开窗口的元素。
window_sum += nums[right] - nums[right - k]
best = max(best, window_sum)
return best
def min_len_at_least(nums, target):
left = 0
window_sum = 0
best = len(nums) + 1
for right, value in enumerate(nums):
window_sum += value
# 条件成立后连续收缩,才能得到以 right 结尾的最短合法窗口。
while window_sum >= target:
best = min(best, right - left + 1)
window_sum -= nums[left]
left += 1
return 0 if best == len(nums) + 1 else best
print(max_sum_fixed([2, 1, 5, 1, 3, 2], 3))
print(min_len_at_least([2, 3, 1, 2, 4, 3], 7))预期输出
9
2第一题的窗口长度一旦达到 k 就固定下来,每轮只需要“一进一出”;第二题则必须使用 while,因为同一个右端点可能对应多个合法窗口,只有持续移动左端,才能找到其中最短的那个。
更新答案的时机决定对错
定长窗口通常在“窗口刚好达到 k”时更新答案。若先更新再移出旧元素,就可能把长度为 k + 1 的非法窗口算进去。
变长窗口要看优化目标。求“最短合法区间”时,应在条件成立的 while 中先更新答案,再移出左端;求“最长合法区间”时,常见模式是先收缩到重新合法,再用当前窗口长度更新最大值。
先验证窗口不变量
写完代码后,优先检查三个不变量:定长窗口更新答案时长度是否恰好为 k;变长窗口进入 while 时条件是否真的成立;左端移出元素后,维护量是否同步更新。
如果条件不具备单调性,例如数组包含负数时用“区间和至少为目标值”做普通双指针,右端扩张与左端收缩都不能保证方向一致,此时就不应强行使用标准滑动窗口。