滑动窗口算法通常应用于处理连续子数组的问题。使用这一技巧的前提往往是数组元素均为正整数,这样才能保证随着窗口的扩大,总和呈现单调递增的特性,从而允许我们在满足条件时收缩左边界。
以 LeetCode 209 题'长度最小的子数组'为例,给定一个含有 n 个正整数的数组和一个正整数 target,找出该数组中满足其和 ≥ target 的长度最小的连续子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。
解决这个问题的核心在于维护一个动态窗口 [left, right]。我们不断向右移动右指针 right,将新元素加入当前窗口和 sum 中。一旦 sum 达到或超过 target,说明当前窗口可能是一个候选解。此时,我们尝试移动左指针 left,缩小窗口,同时更新最小长度,直到 sum 再次小于 target。这个过程确保了我们在遍历一次数组的同时,找到了所有可能的最优解。
下面给出完整的 Python 实现。注意处理边界情况,比如找不到满足条件的子数组时返回 0。
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
ans = n + 1 # 初始化为一个不可能的大值
s = left = 0
for right, x in enumerate(nums):
s += x
# 当窗口和满足条件时,尝试收缩左边界
while s >= target:
ans = min(ans, right - left + 1)
s -= nums[left]
left += 1
return ans if ans != n + 1 else 0
这段代码的时间复杂度是 O(n),因为左右指针都最多遍历整个数组一次。空间复杂度为 O(1)。在实际面试或工程中,这种双指针模式非常常见,关键在于理解何时移动哪一侧指针来维持窗口的性质。


