如何在 Python 中实现滑动窗口

滑动窗口会维护一段连续的元素范围，并在列表或字符串中移动这段范围。在 Python 中，如果每一步的结果都能从上一个窗口更新得出，而不必重新计算窗口中的所有内容，这种模式就很有用。下面的示例展示了三种常见形式：固定大小的窗口、字符不重复的可变窗口，以及满足目标和的窗口。

什么是滑动窗口技术？

窗口是由左、右位置界定的一段范围。它的长度可以固定，也可以随着算法添加或移除元素而变化。窗口中的元素始终连续，因此滑动窗口适用于子数组和子字符串问题；它不能直接表示包含间隔的任意元素组合。

这种技术通常能减少重复计算。例如，算出一个窗口的和之后，只要窗口向前移动一位，就减去移出的值，再加上移入的值。这次更新只需常数时间。总体复杂度取决于具体算法及其使用的数据结构，因此滑动窗口并不保证每个问题都能加速，也不保证每个问题都能达到 O(n) 时间。

使用滑动窗口计算大小为 K 的子数组最大和

给定一个数字列表和正窗口大小 k，先计算最初 k 个值的和。然后让窗口每次向前移动一位，用移出的值和移入的值更新窗口和，并记录遇到的最大和。如果 k 不为正数或大于列表长度，此示例会返回 None，从而明确输入条件。

对于列表 [2, 1, 5, 1, 3, 2] 和 k = 3，各个窗口依次为 [2, 1, 5]、[1, 5, 1]、[5, 1, 3] 和 [1, 3, 2]。程序会输出其中最大的和。若列表长度为 n，算法需要 O(n) 时间和 O(1) 额外空间。

def max_sum_subarray(values, k):
    if k <= 0 or k > len(values):
        return None

    window_sum = sum(values[:k])
    best_sum = window_sum

    for right in range(k, len(values)):
        window_sum += values[right] - values[right - k]
        best_sum = max(best_sum, window_sum)

    return best_sum

values = [2, 1, 5, 1, 3, 2]
k = 3
print(max_sum_subarray(values, k))

此示例代码供你运行；这里不声称已得到任何执行结果。

使用滑动窗口查找不含重复字符的最长子字符串

这个问题要求窗口中不能有重复字符。让右边界沿字符串向右移动，并将每个新字符加入集合。如果新字符已经在集合中，就向右移动左边界，并移除离开窗口的字符，直到重复字符消失。恢复这一条件后，再更新最长长度。

每个边界位置最多向前移动一次，每个字符最多进入和离开集合各一次。因此，对于长度为 n 的字符串，该算法需要 O(n) 时间和 O(min(n, 字母表大小)) 空间。Python 按 Unicode 码点遍历字符串；一个用户感知的字素（例如由基本字母和组合标记组成的字符）可能包含多个码点。

def longest_unique_substring_length(text):
    window_chars = set()
    left = 0
    best_length = 0

    for right, char in enumerate(text):
        while char in window_chars:
            window_chars.remove(text[left])
            left += 1
        window_chars.add(char)
        best_length = max(best_length, right - left + 1)

    return best_length

text = "abcabcbb"
print(longest_unique_substring_length(text))

此示例代码供你运行；这里不声称已得到任何执行结果。

使用滑动窗口查找和至少达到目标值的最短子数组

给定一个目标和，这种方法会查找总和至少达到目标值的最短连续子数组。它要求所有值均为非负数：当当前窗口的和已经足够大时，从左侧移除一个值不会让总和变大，因此可以收缩窗口，寻找更短的有效范围。如果存在负数，这个推理就不成立，需要改用其他算法。

如果不存在符合条件的子数组，该函数会返回 0。当所有值均为非负数且目标值为正数时，每个位置最多被加入和移除各一次，因此算法需要 O(n) 时间和 O(1) 额外空间。目标值不大于零时，代码会将答案视为长度为零的窗口，因为无需任何元素就能达到该目标。

def min_subarray_length(target, values):
    if target <= 0:
        return 0

    left = 0
    running_sum = 0
    shortest = len(values) + 1

    for right, value in enumerate(values):
        running_sum += value
        while running_sum >= target:
            shortest = min(shortest, right - left + 1)
            running_sum -= values[left]
            left += 1

    return 0 if shortest > len(values) else shortest

values = [2, 3, 1, 2, 4, 3]
target = 7
print(min_subarray_length(target, values))

此示例代码供你运行；这里不声称已得到任何执行结果。

总结

滑动窗口有助于分析列表或字符串中的连续范围。窗口大小已知时，可以使用固定窗口；如果范围由字符是否重复或目标和等条件决定，则可以调整窗口边界。使用这种模式之前，应确认窗口移动时能够更新所需状态，并检查算法的前提是否符合输入。这些示例涵盖了常见的 Python 面试题，但遇到其他约束时，可能需要采用不同的方法。

常见问题

1. 什么时候适合使用滑动窗口？ 当问题涉及连续子数组或子字符串，而且移动一个或两个边界时可以更新当前结果，就可以考虑使用它。
2. 每种滑动窗口算法的时间复杂度都是 O(n) 吗？ 不是。这些示例之所以是线性时间，是因为边界移动次数和每步更新的工作量都有界。其他算法每次移动时可能需要进行更多操作。
3. 这个最小和窗口算法可以处理负数吗？ 按当前写法不行。它的收缩规则依赖所有值均为非负数；移除一个负数后，总和可能反而增大。
4. 子数组和子序列有什么区别？ 子数组中的元素必须连续。子序列可以在保持顺序的同时跳过某些位置，因此窗口无法枚举所有子序列。