跳到主要内容

滑动窗口技巧

什么是滑动窗口技巧？​

滑动窗口技巧是一种用于解决数组或字符串相关问题的算法设计方法。它通过维护一个“窗口”（通常是数组或字符串的一个子集），在数据上滑动这个窗口来高效地解决问题。滑动窗口技巧通常用于解决需要计算连续子数组或子字符串的问题，例如求最大子数组和、最长无重复字符子串等。

滑动窗口技巧的核心思想是避免重复计算。通过调整窗口的起始和结束位置，可以在线性时间内解决问题，而不需要嵌套循环。

滑动窗口的基本实现​

滑动窗口通常有两种类型：

  1. 固定大小的窗口：窗口的大小是固定的，例如求长度为 k 的子数组的最大和。
  2. 可变大小的窗口：窗口的大小根据条件动态调整，例如求最长无重复字符的子串。

固定大小的窗口示例​

假设我们需要计算一个数组中长度为 k 的连续子数组的最大和。

python
def max_sum_subarray(arr, k):
    max_sum = float('-inf')
    window_sum = 0
    left = 0

    for right in range(len(arr)):
        window_sum += arr[right]

        # 当窗口大小达到 k 时
        if right >= k - 1:
            max_sum = max(max_sum, window_sum)
            window_sum -= arr[left]  # 移除最左边的元素
            left += 1  # 滑动窗口

    return max_sum

输入：

python
arr = [2, 1, 5, 1, 3, 2]
k = 3

输出：

python
9  # 子数组 [5, 1, 3] 的和最大

可变大小的窗口示例​

假设我们需要找到一个字符串中最长的无重复字符的子串。

python
def longest_substring_without_repeating_characters(s):
    char_index_map = {}
    max_length = 0
    left = 0

    for right in range(len(s)):
        if s[right] in char_index_map:
            # 如果字符已经出现过，更新左边界
            left = max(left, char_index_map[s[right]] + 1)
        
        # 更新字符的最新索引
        char_index_map[s[right]] = right
        # 计算当前窗口的长度
        max_length = max(max_length, right - left + 1)

    return max_length

输入：

python
s = "abcabcbb"

输出：

python
3  # 最长无重复字符的子串是 "abc"

滑动窗口的实际应用场景​

滑动窗口技巧在许多实际问题中都有广泛应用，以下是一些常见的场景：

  1. 最大子数组和：给定一个数组和一个整数 k，找到长度为 k 的子数组的最大和。
  2. 最长无重复字符子串：给定一个字符串，找到其中不包含重复字符的最长子串。
  3. 最小覆盖子串：给定一个字符串 s 和一个字符串 t，找到 s 中包含 t 所有字符的最短子串。
  4. 字符串排列：给定两个字符串 s1 和 s2，判断 s2 是否包含 s1 的排列。

滑动窗口的优化技巧​

滑动窗口技巧的核心在于如何高效地调整窗口的边界。以下是一些优化技巧：

  1. 使用哈希表记录字符索引：在解决字符串问题时，哈希表可以帮助快速查找字符是否重复。
  2. 提前终止：在某些情况下，如果已经找到满足条件的最优解，可以提前终止循环。
  3. 双指针：滑动窗口通常使用双指针（左指针和右指针）来表示窗口的边界。

总结​

滑动窗口技巧是一种高效的算法设计方法，特别适合解决数组或字符串中的连续子集问题。通过维护一个窗口并动态调整其边界，可以避免重复计算，从而在时间复杂度上取得优势。

提示

滑动窗口技巧的关键在于理解窗口的边界如何移动，以及如何利用数据结构（如哈希表）来优化查找操作。

附加资源与练习​

  1. 练习 1：实现一个函数，找到数组中所有长度为 k 的子数组的平均值。
  2. 练习 2：给定一个字符串 s 和一个整数 k，找到包含最多 k 个不同字符的最长子串。
  3. 推荐阅读：

通过不断练习和深入理解，你将能够熟练掌握滑动窗口技巧，并应用于更复杂的算法问题中。