滑动窗口|| python ||数据结构和算法

滑动窗口技术详解：高效解决子数组问题

滑动窗口是一种在数组或字符串等输入数据中定义窗口（或范围）并移动该窗口以执行特定操作的技术。它广泛应用于算法中，例如查找特定和的子数组、查找具有唯一字符的最长子字符串等。

滑动窗口主要分为两种类型：

1. 固定大小滑动窗口: 窗口大小固定不变，窗口在数据中逐个元素移动。
2. 可变大小滑动窗口: 窗口大小动态调整。右指针每次迭代递增，只有在不满足特定条件时才移动左指针。左指针持续移动直到条件再次满足或到达右指针。

何时使用滑动窗口？

当需要计算最大或最小子数组，或执行任何与子数组相关的操作时，滑动窗口通常是高效的解决方案。

滑动窗口通用模板:

function fn(arr):
    left = 0
    for (int right = 0; right < arr.length; right++):
        // 在窗口内执行操作
        // ...
        // 根据条件调整左指针 left
        // ...

示例：最小长度子数组和

给定一个正整数数组 nums 和一个正整数目标 target，找到总和大于等于 target 的子数组的最小长度。如果没有这样的子数组，则返回 0。

测试用例:

• 输入: target = 7, nums = [2,3,1,2,4,3] 输出: 2 (子数组 [4,3] 长度最小)
• 输入: target = 4, nums = [1,4,4] 输出: 1
• 输入: target = 11, nums = [1,1,1,1,1,1,1,1] 输出: 0

暴力法:

暴力法的时间复杂度为 O(n³)。

滑动窗口法:

算法:

1. 初始化左右指针 left 和 right，以及变量 currentSum (当前窗口和) 和 minLen (最小窗口长度)。
2. 每次迭代递增 right 指针。
3. 检查窗口和是否大于等于 target。如果大于等于，则尝试缩小窗口，移动 left 指针直到窗口和不再满足条件，并更新 minLen。
4. 继续迭代直到 right 指针遍历完数组。

时间复杂度: O(n) 空间复杂度: O(1)

通过滑动窗口算法，我们将时间复杂度从 O(n³) 降低到 O(n)。