滑动窗口算法精讲：从入门到精通 – wiki基地

作者： /

滑动窗口算法精讲：从入门到精通

滑动窗口算法（Sliding Window Algorithm）是一种常用的算法技巧，尤其在处理数组、字符串等线性结构的问题时非常高效。它主要用于解决那些需要在一个较大范围内寻找满足特定条件的连续子区间的问题。滑动窗口的核心思想在于维护一个“窗口”，这个窗口在数据序列上滑动，通过动态调整窗口的边界，避免不必要的重复计算，从而降低时间复杂度。

1. 滑动窗口算法的基本概念

1.1 什么是滑动窗口？

想象一下，你有一个固定大小的窗户，你透过这个窗户观察一条长长的街道。你沿着街道移动窗户，每次只观察窗户内的景象。这就是滑动窗口的形象化比喻。

在算法中，滑动窗口通常由两个指针（左指针和右指针）来表示。这两个指针之间的区域就是“窗口”。窗口的大小可以是固定的，也可以是动态变化的。

1.2 为什么要使用滑动窗口？

许多问题都可以用暴力解法解决，即遍历所有可能的子区间。但是，这种方法通常会导致大量的重复计算，时间复杂度很高（通常是 O(n^2) 或 O(n^3)）。

滑动窗口算法通过巧妙地利用已经计算过的信息，避免重复计算，将时间复杂度降低到 O(n)。这是因为窗口在滑动过程中，每次只需要更新窗口边界附近的信息，而不需要重新计算整个窗口的内容。

1.3 滑动窗口的类型

滑动窗口主要有两种类型：

  • 固定大小窗口： 窗口的大小是固定的，不会随着滑动过程而改变。这种类型的窗口适用于解决那些需要查找固定长度子区间的问题。
  • 可变大小窗口： 窗口的大小是动态变化的，可以根据需要扩大或缩小。这种类型的窗口适用于解决那些需要查找满足特定条件的最长或最短子区间的问题。

2. 滑动窗口算法的框架

虽然滑动窗口算法的具体实现会因问题而异，但它们通常遵循一个基本的框架。下面是一个通用的滑动窗口算法模板（以可变大小窗口为例，使用Python）：

“`python
def sliding_window(s: str, target: …) -> …:
“””
滑动窗口算法模板 (可变大小窗口)

Args:
    s: 输入的字符串或数组
    target: 目标值或其他条件

Returns:
    根据具体问题返回结果 (例如，子串的起始位置、长度等)
"""

# 1. 初始化窗口的两端 (通常是数组或字符串的起始位置)
left = 0
right = 0

# 2. 初始化一个字典或其他数据结构来存储窗口内元素的信息
window = {}  # 例如，用字典记录窗口内每个字符的出现次数

# 3. 初始化其他必要的变量 (例如，记录最小/最大长度、有效字符数等)
valid = 0  # 用于判断窗口内是否满足条件
min_len = float('inf')  # 记录最小长度 (根据问题可能需要最大长度)
start = 0 #记录起始位置

# 4. 开始滑动窗口 (右指针向右移动)
while right < len(s):
    # c 是将移入窗口的字符
    c = s[right]
    # 增大窗口
    right += 1
    # 进行窗口内数据的一系列更新
    # ... (例如，更新 window 字典、更新 valid 等)

    # 5. 判断左侧窗口是否要收缩 (根据问题的条件)
    while valid: # or some other condition
        # d 是将移出窗口的字符
        d = s[left]
        # 缩小窗口
        left += 1
        # 进行窗口内数据的一系列更新
        # ... (例如，更新 window 字典、更新 valid 等)

        # 在这里更新答案
        if (right - left) < min_len:
            min_len = (right - left)
            start = left -1

# 6. 返回结果 (根据具体问题)
return "" if min_len == float('inf') else s[start:start + min_len]

“`

模板解释：

  1. 初始化： 设置窗口的左右边界（left 和 right），通常都从 0 开始。同时，初始化一个数据结构（例如，window 字典）来存储窗口内的元素信息，以及其他必要的变量（例如，valid、min_len 等）。

  2. 扩大窗口： 右指针 right 向右移动，将新的元素纳入窗口。同时，更新 window 字典和其他相关变量。

  3. 判断并收缩窗口： 根据题目的条件，判断是否需要收缩窗口。如果满足收缩条件（例如，窗口内的元素已经满足了题目的要求），则左指针 left 向右移动，将元素移出窗口。同时，更新 window 字典和其他相关变量。

  4. 更新结果： 在每次收缩窗口时（或者在扩大窗口时，取决于具体问题），更新最终的结果（例如，最小长度、最大长度、子串的起始位置等）。

  5. 循环： 重复步骤 2-4，直到右指针 right 到达输入序列的末尾。

  6. 返回结果： 根据题目的要求，返回最终的结果。

3. 经典例题解析

下面通过几个经典的例题来详细讲解滑动窗口算法的应用。

3.1 最小覆盖子串 (LeetCode 76)

题目描述： 给你一个字符串 s 和一个字符串 t。请你在 s 中找出包含 t 的所有字符的最短子串。如果 s 中不存在这样的子串，则返回空字符串 “”。

示例：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

解题思路：

  1. 初始化： 使用 left 和 right 指针表示窗口的左右边界。使用 window 字典记录窗口内每个字符出现的次数，使用 need 字典记录 t 中每个字符出现的次数。使用 valid 变量记录窗口内满足 t 中字符要求的字符个数。
  2. 扩大窗口： right 指针向右移动，将新的字符 c 纳入窗口。如果 c 是 t 中的字符，则更新 window[c] 和 valid。
  3. 收缩窗口： 当 valid 等于 len(need) 时，表示窗口内已经包含了 t 的所有字符。此时，尝试收缩窗口：left 指针向右移动，将字符 d 移出窗口。如果 d 是 t 中的字符，则更新 window[d] 和 valid。
  4. 更新结果： 在每次收缩窗口时，更新最小子串的长度和起始位置。
  5. 循环： 重复步骤 2-4，直到 right 到达 s 的末尾。
  6. 返回结果： 返回最小子串。

代码实现（Python）：

“`python
def minWindow(s: str, t: str) -> str:
need = {}
window = {}
for c in t:
need[c] = need.get(c, 0) + 1

left = 0
right = 0
valid = 0
min_len = float('inf')
start = 0

while right < len(s):
    c = s[right]
    right += 1

    if c in need:
        window[c] = window.get(c, 0) + 1
        if window[c] == need[c]:
            valid += 1

    while valid == len(need):
        if (right - left) < min_len:
            min_len = (right - left)
            start = left

        d = s[left]
        left += 1

        if d in need:
            if window[d] == need[d]:
                valid -= 1
            window[d] -= 1

return "" if min_len == float('inf') else s[start:start + min_len]

“`

3.2 无重复字符的最长子串 (LeetCode 3)

题目描述： 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例：

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

解题思路：

  1. 初始化： left 和 right 指针都从 0 开始。使用 window 字典记录窗口内每个字符出现的次数。
  2. 扩大窗口： right 指针向右移动，将新的字符 c 纳入窗口。更新 window[c]。
  3. 收缩窗口： 如果 window[c] 大于 1，说明出现了重复字符。此时，left 指针向右移动，将字符 d 移出窗口，直到 window[c] 等于 1。
  4. 更新结果： 在每次扩大窗口后（注意不是收缩窗口后），更新最长子串的长度。
  5. 循环： 重复步骤 2-4，直到 right 到达 s 的末尾。
  6. 返回结果： 返回最长子串的长度。

代码实现（Python）：

“`python
def lengthOfLongestSubstring(s: str) -> int:
window = {}
left = 0
right = 0
max_len = 0

while right < len(s):
    c = s[right]
    right += 1
    window[c] = window.get(c, 0) + 1

    while window[c] > 1:
        d = s[left]
        left += 1
        window[d] -= 1

    max_len = max(max_len, right - left)  # 更新结果在扩大窗口后

return max_len

“`

3.3 长度最小的子数组 (LeetCode 209)

题目描述: 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

解题思路:
1. 初始化: left 和 right 指针都从 0 开始。window_sum记录当前窗口内元素的和。 min_length记录最小长度，初始化为无穷大。
2. 扩大窗口: right 指针向右移动， 将新的元素加入窗口中，更新window_sum.
3. 收缩窗口: 当window_sum >= target 时，更新最小长度min_length，然后left指针向右移动，并将移出窗口的元素从window_sum中减去，直到window_sum < target。
4. 循环: 重复步骤2-3，直到right到达数组末尾。
5. 返回结果: 返回min_length, 如果min_length仍然是无穷大，则返回0。

代码实现（Python）:

“`python
def minSubArrayLen(target: int, nums: list[int]) -> int:
left = 0
right = 0
window_sum = 0
min_length = float(‘inf’)

while right < len(nums):
    window_sum += nums[right]
    right += 1

    while window_sum >= target:
        min_length = min(min_length, right - left)
        window_sum -= nums[left]
        left += 1
return 0 if min_length == float('inf') else min_length

“`

3.4 字符串的排列 (LeetCode 567)

题目描述: 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。 换句话说，s1 的排列之一是 s2 的 子串 。

示例：
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba")。

解题思路:
1. 初始化: 用need字典记录s1中每个字符出现的次数。 window字典记录当前窗口内字符出现的次数。 left和right指针都从0开始。valid记录满足need中字符数量的字符个数。
2. 扩大窗口: right指针向右移动, 将新的字符加入窗口。 如果新加入的字符在need中，更新window和valid。
3. 判断: 当right - left == len(s1)时，表示窗口大小已经和s1长度相等。此时判断valid是否等于len(need)，如果相等，则返回True。
4. 收缩窗口: 不论上一步是否返回True, 都要收缩窗口。left指针向右移动，如果移出的字符在need中，更新window和valid。
5. 循环:重复2-4步， 直到right指针到达s2末尾。
6. 返回结果: 如果循环结束仍然没有返回True，则返回False

代码实现（Python）:

“`python
def checkInclusion(s1: str, s2: str) -> bool:
need = {}
for char in s1:
need[char] = need.get(char, 0) + 1

window = {}
left = 0
right = 0
valid = 0

while right < len(s2):
    c = s2[right]
    right += 1

    if c in need:
        window[c] = window.get(c, 0) + 1
        if window[c] == need[c]:
            valid += 1

    if right - left == len(s1):  #窗口大小等于s1长度
        if valid == len(need):
            return True

        d = s2[left]
        left += 1
        if d in need:
            if window[d] == need[d]:
                valid -= 1
            window[d] -= 1
return False

“`

4. 滑动窗口算法的优化技巧

  • 数据结构的选择： 根据问题的特点选择合适的数据结构来存储窗口内的信息。例如，如果需要统计字符出现的次数，可以使用字典（哈希表）；如果需要维护窗口内元素的有序性，可以使用有序集合或平衡二叉搜索树。
  • 提前判断： 在一些情况下，可以在滑动窗口的过程中提前判断是否能够得到满足条件的结果，从而避免不必要的计算。
  • 双指针技巧： 在某些问题中，可能需要使用多个指针来维护窗口的不同部分，或者使用快慢指针来解决问题。例如找到数组的中间节点可以用快慢指针， 快指针一次走两步，慢指针一次走一步，当快指针走到结尾，慢指针就在中间。

5. 总结

滑动窗口算法是一种非常实用的算法技巧，它可以有效地解决许多与子区间相关的问题。掌握滑动窗口算法的关键在于理解其核心思想，即通过动态调整窗口的边界来避免重复计算。通过学习本文提供的框架和例题，相信你已经对滑动窗口算法有了更深入的理解。在实际应用中，需要根据具体问题的特点灵活运用滑动窗口算法，并结合适当的优化技巧，才能写出高效、简洁的代码。 多加练习，熟能生巧！

发表评论

您的邮箱地址不会被公开。 必填项已用 * 标注

滚动至顶部