固定大小和动态调整

滑动窗口（Sliding Window）是一种高效的算法设计模式，主要用于解决数组或字符串中具有连续性约束的问题。通过维护一个动态调整大小的窗口，可以在O（n）的时间复杂度内完成某些统计或搜索任务。以下是关于Python中滑动窗口的详细解析与实战案例：

一、核心概念

1. 窗口（Window） ：由起始指针start和结束指针end组成，表示当前关注的子集范围。

2. 滑动（Sliding） ：通过移动start或end指针调整窗口位置，动态扩展或收缩窗口边界。

3. 动态调整 ：根据问题需求，窗口大小可固定或动态变化，例如：

   • 固定窗口：如计算连续子数组的最大和

   • 动态窗口：如滑动窗口最大值/最小值查询

二、典型应用场景

1. 连续子数组/字符串匹配

   • 示例 ：给定数组nums和目标值k，找出所有和为k的连续子数组。

   • 实现步骤 ：初始化窗口为``，通过移动end指针扩展窗口，当窗口和超过k时移动start指针收缩窗口，记录满足条件的子数组。

2. 滑动窗口最大值/最小值

   • 示例 ：在数组中找到长度为k的连续子数组的最大值。

   • 优化 ：使用双端队列（deque）维护窗口内的元素索引，保持队列头部为当前窗口的最大值索引，通过滑动窗口更新队列。

3. 数据流处理

   • 适用于实时数据处理场景，如股票价格分析、网络流量监控等，通过固定窗口统计滑动窗口内的统计信息。

三、实现步骤与代码示例

1. 固定窗口大小

示例 ：计算数组中连续k个数的最大和。

def max_sum_sliding_window(arr, k=3):
    if not arr or len(arr) < k:
        return None
    current_sum = sum(arr[:k])
    max_sum = current_sum
    for i in range(k, len(arr)):
        current_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, current_sum)
    return max_sum

# 测试
arr = [1, 4, 2, 10, 23, 3, 1, 0, 20]
print(max_sum_sliding_window(arr))  # 输出: 36 (23+3+10)

2. 动态调整窗口

示例 ：找到和为k的连续子数组。

def find_subarrays_with_sum(nums, k):
    start = 0
    current_sum = 0
    result = []
    for end in range(len(nums)):
        current_sum += nums[end]
        while current_sum > k and start <= end:
            current_sum -= nums[start]
            start += 1
        if current_sum == k:
            result.append(nums[start:end+1])
    return result

# 测试
nums = [1, 1, 3, 4, 2, 0, 5]
print(find_subarrays_with_sum(nums, 5))  # 输出: [[1, 1, 3, 0], [3, 4, 2, 0]]

四、注意事项

1. 边界条件处理 ：需检查数组长度是否满足窗口大小要求，避免索引越界。

2. 数据结构优化 ：使用双端队列可降低时间复杂度至O（n）（针对最大值/最小值问题）。

3. 适用场景选择 ：滑动窗口适合连续数据且窗口大小相对固定的场景，对于非连续或随机窗口需求需谨慎使用。

五、扩展应用

• 时间序列分析 ：通过滑动窗口计算滑动窗口内的统计量（如均值、标准差）。

• 图像处理 ：实现图像的局部特征提取（如边缘检测）。

通过灵活运用滑动窗口技术，可显著提升算法效率，尤其适用于需要频繁更新窗口统计的场景。