滑动窗口算法

Jessica Gracewell2023-10-172023-10-17

滑动窗口算法

滑动窗口算法是一种常用于解决数组/字符串子元素问题的算法。它可以有效地降低问题的复杂性，从而降低解决问题的时间复杂度。滑动窗口的主要思想是维护一个窗口，并根据具体的问题需求移动这个窗口。

1.基本概念

窗口： 这通常是一个连续的子集或子序列，它可以是固定大小或可变大小。
窗口滑动： 这涉及到两个操作：移动窗口的左边界和移动窗口的右边界。通常，我们会固定其中一个边界并移动另一个边界。
条件满足： 根据问题，窗口可以在满足某些条件或不满足某些条件时进行调整。

基础案例：找出数组中的最大连续子数组的和。

问题描述： 给定一个整数数组 nums，找到一个具有最大和的连续子数组（至少包含一个数字）并返回其和。

例如：

nums = [-2,1,-3,4,-1,2,1,-5,4]

最大连续子数组的和为 [4,-1,2,1]，和为 6。

解决方案：

我们可以使用滑动窗口的方法解决这个问题，窗口的大小是可变的。

def max_sub_array(nums):
    # 初始情况下窗口的和为数组的第一个元素
    current_sum = max_sum = nums[0]
    
    # 从第二个元素开始，滑动窗口
    for num in nums[1:]:
        # 如果当前元素加上当前的和比当前元素还小，则重置窗口开始位置
        current_sum = max(num, current_sum + num)
        
        # 更新最大和
        max_sum = max(max_sum, current_sum)
    
    return max_sum

这个方法的时间复杂度是$O(n)$，其中n是数组的长度。

2. 固定大小的滑动窗口

滑动窗口算法博客 - 第二部分
2. 固定大小的滑动窗口

固定大小的滑动窗口是一个常见的滑动窗口算法变种。在这种方法中，窗口的大小始终保持不变，并通过数组或字符串进行滑动。

基本概念：

窗口大小： 事先确定，并在整个算法执行过程中保持不变。
滑动方式： 窗口从左向右滑动，每次滑动一个单位。

案例1：计算数组中大小为k的所有子数组的平均值

问题描述：给定一个数组和一个整数k，找出大小为k的所有连续子数组的平均值。

例如：

nums = [1, 3, 2, 6, -1, 4, 1, 8, 2]
k = 5

结果为：[2.2, 2.8, 2.4, 3.6, 2.8]

解决方案：


def find_averages_of_subarrays(k, arr):
    result = []
    window_sum, window_start = 0.0, 0
    
    # 使用右边界i来遍历数组
    for i in range(len(arr)):
        window_sum += arr[i]  # 累加到当前窗口的和
        
        # 当窗口大小达到k时
        if i >= k-1:
            result.append(window_sum / k)  # 计算平均值并保存
            window_sum -= arr[window_start]  # 减去窗口最左边的值
            window_start += 1  # 将窗口左边界向右移动一位
    
    return result

案例2：找到数组中的最大连续k个元素的和

问题描述：给定一个数组，找到连续k个元素的最大和。

例如：

nums = [2, 3, 4, 1, 5]
k = 2

结果为：7（因为 [3,4] 的和为7）

解决方案：

def max_sum_subarray_of_size_k(k, arr):
    max_sum , window_sum = 0, 0
    window_start = 0

    for window_end in range(len(arr)):
        window_sum += arr[window_end]  # 加入窗口右边界的元素
        
        if window_end >= k-1:  # 当窗口大小达到k
            max_sum = max(max_sum, window_sum)  # 更新最大和
            window_sum -= arr[window_start]  # 移除窗口最左边的元素
            window_start += 1  # 窗口左边界向右移动

    return max_sum

3. 可变大小的滑动窗口

与固定大小的窗口不同，可变大小的滑动窗口根据满足的条件动态调整其大小。这种方法在处理复杂问题时尤其有用。

基本概念：

窗口调整： 窗口的大小可以增大或缩小，通常基于某些条件。
滑动方式： 与固定窗口类似，通常由右边界决定何时增大窗口，由左边界决定何时缩小窗口。

案例1：最小子数组的和大于或等于给定值

问题描述：给定一个数组和一个数值S，找到数组中连续的最小子数组，其和大于或等于S。

例如：

nums = [2, 1, 5, 2, 3, 2]
S = 7

结果为：2（因为 [5,2] 或 [2,3,2] 都满足条件，但前者长度最小）

解决方案：

def min_sub_array_len(S, nums):
    total = 0
    start = 0
    min_len = float('inf')

    for end in range(len(nums)):
        total += nums[end]  # 加入窗口的右边界元素
        
        # 当子数组的和达到或超过S时
        while total >= S:
            # 更新最小长度
            min_len = min(min_len, end - start + 1)
            total -= nums[start]  # 移除窗口的最左边元素
            start += 1  # 窗口左边界向右移动

    return min_len if min_len != float('inf') else 0

案例2：找到字符串中的最长无重复字符子串

问题描述：给定一个字符串，找出其中没有重复字符的最长子串。

例如：

s = "abcabcbb"

结果为：3（因为答案是 “abc”，其长度为3）

解决方案：


def length_of_longest_substring(s):
    if not s:
        return 0

    char_index_map = {}  # 存储字符及其索引
    max_len = 0
    start = 0

    for end, char in enumerate(s):
        # 如果字符已经在窗口内
        if char in char_index_map:
            # 移动窗口左边界到重复字符的下一个位置
            start = max(start, char_index_map[char] + 1)
        
        # 更新字符的位置
        char_index_map[char] = end
        # 更新最大长度
        max_len = max(max_len, end - start + 1)

    return max_len

4. 用滑动窗口解决字符串问题

处理字符串问题时，滑动窗口特别有效，尤其是当问题涉及子串、子序列或字符重复等方面时。

基本概念：

字符映射： 通常使用字典来追踪当前窗口中的字符及其出现的次数。
窗口条件： 窗口的移动和大小调整通常基于字符串中的字符出现频率或其他条件。

案例1：找到字符串中所有的字母异位词

例如：

s = "cbaebabacd"
p = "abc"

结果为：[0, 6]

解决方案：

def find_anagrams(s, p):
    # 使用字典记录p中的每个字符及其频率
    char_count = {}
    for char in p:
        char_count[char] = char_count.get(char, 0) + 1

    start = 0
    matched = 0
    indices = []

    # 遍历字符串s
    for end in range(len(s)):
        # 如果当前字符在字典中，则减少对应的计数
        if s[end] in char_count:
            char_count[s[end]] -= 1
            if char_count[s[end]] == 0:
                matched += 1
        
        # 当所有字符的频率都匹配时，记录开始索引
        if matched == len(char_count):
            indices.append(start)
        
        # 保持窗口大小与p相同
        if end >= len(p) - 1:
            if s[start] in char_count:
                if char_count[s[start]] == 0:
                    matched -= 1
                char_count[s[start]] += 1
            start += 1

    return indices

案例2：最小覆盖子串

例如：

s = "ADOBECODEBANC"
t = "ABC"

结果为：“BANC”

解决方案：

def min_window(s, t):
    if not s or not t:
        return ""

    # 使用字典记录t中的每个字符及其频率
    char_count = {}
    for char in t:
        char_count[char] = char_count.get(char, 0) + 1

    required = len(char_count)
    matched = 0
    min_len = float('inf')
    window_start = 0
    substring_start = 0

    for window_end in range(len(s)):
        # 如果当前字符在字典中，则减少对应的计数
        if s[window_end] in char_count:
            char_count[s[window_end]] -= 1
            if char_count[s[window_end]] == 0:
                matched += 1
        
        # 当所有字符的频率都匹配时，尝试缩小窗口以找到最小的子串
        while matched == required:
            if window_end - window_start < min_len:
                min_len = window_end - window_start
                substring_start = window_start
            
            left_char = s[window_start]
            if left_char in char_count:
                char_count[left_char] += 1
                if char_count[left_char] > 0:
                    matched -= 1
            
            window_start += 1

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

5. 滑动窗口与其他数据结构的结合

滑动窗口并不总是单独使用，有时与其他数据结构结合可以更有效地解决问题，例如队列、双端队列或哈希表。

基本概念：

数据结构辅助： 使用其他数据结构可以帮助我们更快地跟踪和更新窗口内的元素状态。
案例1：滑动窗口最大值
问题描述： 给定一个数组nums和一个整数k，返回在每一个大小为k的窗口从左到右滑动时的最大值。

例如：

nums = [1,3,-1,-3,5,3,6,7]
k = 3

结果为：[3,3,5,5,6,7]

解决方案：使用双端队列存储元素索引，保证队列头部始终是当前窗口的最大值。

from collections import deque

def max_sliding_window(nums, k):
    if not nums:
        return []

    # 初始化双端队列和结果列表
    deq, res = deque(), []

    for i in range(len(nums)):
        # 移除滑出窗口的元素索引
        while deq and deq[0] < i - k + 1:
            deq.popleft()

        # 从后面移除所有小于当前元素的索引，确保队列的第一个元素是当前窗口的最大值
        while deq and nums[deq[-1]] < nums[i]:
            deq.pop()

        deq.append(i)  # 添加当前元素索引
        if i >= k - 1:  # 从k-1开始，我们已经有完整的大小为k的窗口
            res.append(nums[deq[0]])  # 队列的头部为当前窗口的最大值

    return res

案例2：长度最小的子数组

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

例如：

nums = [2,3,1,2,4,3]
target = 7

结果为：2（子数组是 [4,3]）

解决方案：使用滑动窗口配合双端队列来寻找答案。

def min_sub_array_len(target, nums):
    total, start, min_len = 0, 0, float('inf')

    for end in range(len(nums)):
        total += nums[end]  # 将当前元素加入到总和中
        
        # 当总和达到或超过target时
        while total >= target:
            min_len = min(min_len, end - start + 1)
            total -= nums[start]  # 移除滑出窗口的元素
            start += 1  # 窗口左边界向右移动

    return min_len if min_len != float('inf') else 0

6. 滑动窗口的变种与优化

滑动窗口不只是一种单一的方法，它有许多变种和优化策略，可以根据问题的特点进行调整。

基本概念：

变种： 不同于固定大小的滑动窗口，可以使用动态调整大小的窗口。
优化： 在某些情况下，可以使用额外的数据结构或逻辑来优化滑动窗口的性能。

案例1：最大连续1的个数 III

问题描述：给定一个二进制数组，你可以将其上的 k 个 0 变为 1，返回仅包含 1 的最长（连续）子数组的长度。

例如：

nums = [1,0,1,1,0,1]
k = 1

结果为：4

解决方案：使用一个动态的滑动窗口，窗口的大小减去窗口内的1的数量等于k。

def longest_ones(nums, k):
    left, right = 0, 0
    max_len = 0

    for right in range(len(nums)):
        # 如果当前数是0，k减1
        if nums[right] == 0:
            k -= 1

        # 如果k小于0，窗口左边界移动
        while k < 0:
            if nums[left] == 0:
                k += 1
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len

案例2：连续子数组的平均值

问题描述：给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

例如：

nums = [1,12,-5,-6,50,3]
k = 4

结果为：12.75

解决方案：使用滑动窗口来计算累积和，然后求平均值。

def find_max_average(nums, k):
    # 先计算前k个元素的总和
    window_sum = sum(nums[:k])
    max_sum = window_sum

    # 使用滑动窗口计算后面的连续子数组的总和
    for i in range(k, len(nums)):
        window_sum = window_sum - nums[i - k] + nums[i]
        max_sum = max(max_sum, window_sum)

    # 返回平均值
    return max_sum / k

滑动窗口算法大总结 🎉

同学们，经过了六部分的紧张刺激、起起落落的滑动窗口之旅，我们终于到达了终点站！😁

首先，给大家一个大大的赞👍！你们真的太棒了！

滑动窗口听起来像不是在玩滑翔伞吗？🪂 而实际上，它更像是你手上的那个"魔法滑板"，让你在编程的海洋里轻松滑行！🛹

那么，我们一起回顾一下我们学到了什么：

基础篇： 就像学走路一样，我们从最基础的滑动窗口开始，找到数组的最大子数组之和。简单但不平凡！🏃
字符串篇： 犹如在复杂的迷宫中找到正确的出路，我们学会了如何处理那些棘手的字符串问题。💡
结合其他数据结构： 就像超级英雄需要小伙伴一样，滑动窗口有时也需要其他数据结构的帮助，使其威力更大！💪
变种与优化篇： 最后，我们更进一步，探索了滑动窗口的一些变种和高级技巧，就像学会了滑翔伞上的特技动作！🎩

现在，当你面对一个问题时，希望你能像一个骄傲的滑翔伞手，自信地打开你的滑动窗口，享受编程的快感！

在结束前，我有一个小建议：不要让这个“滑板”吃灰哦！经常使用，让滑动窗口成为你编程工具箱中的得力助手！

再见了，勇敢的编程者！🚀 让我们在代码的世界里再次相遇！👩‍💻👨‍💻

愿你每天都像滑动窗口一样，滑过生活的高低，享受其中的快乐！🥳🎈🎉

滑动窗口算法

1.基本概念

基础案例： 找出数组中的最大连续子数组的和。

解决方案：

2. 固定大小的滑动窗口

基本概念：

案例1：计算数组中大小为k的所有子数组的平均值

解决方案：

案例2：找到数组中的最大连续k个元素的和

解决方案：

3. 可变大小的滑动窗口

基本概念：

案例1：最小子数组的和大于或等于给定值

解决方案：

案例2：找到字符串中的最长无重复字符子串

解决方案：

4. 用滑动窗口解决字符串问题

基本概念：

案例1：找到字符串中所有的字母异位词

解决方案：

案例2：最小覆盖子串

解决方案：

5. 滑动窗口与其他数据结构的结合

基本概念：

解决方案：使用双端队列存储元素索引，保证队列头部始终是当前窗口的最大值。

案例2：长度最小的子数组

解决方案：使用滑动窗口配合双端队列来寻找答案。

6. 滑动窗口的变种与优化

基本概念：

案例1：最大连续1的个数 III

解决方案：使用一个动态的滑动窗口，窗口的大小减去窗口内的1的数量等于k。

案例2：连续子数组的平均值

解决方案：使用滑动窗口来计算累积和，然后求平均值。

滑动窗口算法大总结 🎉

Jessica Gracewell

基础案例：找出数组中的最大连续子数组的和。