03. 滑动窗口

0 - 算法, 0.0 - 算法模版 本文总阅读量次

正文

滑动窗口（Sliding Window）是一种在数组或字符串上执行操作的优化技术。它将嵌套循环的问题转化为单个循环，从而显著降低时间复杂度。

算法模板（固定窗口大小）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
fun slidingWindow(nums: IntArray, k: Int): Int {
    val n = nums.size
    if (n < k) return 0
    
    var sum = 0
    var maxSum = 0

    // 1. 初始化：计算第一个窗口的和
    for (i in 0 until k) {
        sum += nums[i]
    }

    maxSum = sum

    // 2. 滑动：从第 k 个元素开始遍历
    for (i in k until n) {
        // 新窗口的和 = 前一个窗口的和 + 新进入的元素 - 离开窗口的元素
        sum += nums[i] - nums[i - k]
        // 更新结果
        maxSum = maxOf(maxSum, sum)
    }

    return maxSum
}

使用说明

  1. 适用场景：

    • 固定窗口：给定窗口大小 $k$，求最大/最小和、平均值等。
    • 可变窗口：寻找满足特定条件的最长/最短子数组（通常配合双指针 left, right 使用）。

  2. 核心优势：

    • 避免了重复计算窗口重叠部分的值。
    • 时间复杂度通常为 $O(N)$。

  3. 注意点：

    • 注意边界条件，如数组长度小于 $k$ 的情况。
    • 如果是求平均值，注意浮点数转换。
    • 对于可变窗口，通常逻辑是：右边界右移增加元素 -> 窗口不满足条件时左边界右移移除元素。
0 - 算法, 0.0 - 算法模版