滑动窗口法

3.1 滑动窗口法的定义。

滑动窗口法 (Sliding Window) 是一种技术， 用于解决数组或字符串问题，通过在数据上移动固定大小的子数组（或子字符串）， 以寻找最佳解决方案。它允许在固定大小的窗口中处理元素， 并根据问题的条件动态调整窗口。

这个技巧特别适用于与数据序列相关的问题，如数组或字符串， 并有助于降低与更简单方法相比的时间复杂度。

基本原则

• 窗口初始化: 将窗口的开始和结束设置在初始位置。
• 移动窗口: 逐步移动窗口边界，从一侧添加元素，从另一侧删除元素。
• 处理窗口: 在每一步执行当前窗口所需的计算。

滑动窗口法的时间和空间复杂度

时间复杂度:

• O(n) — 在大多数情况下，因为指针或窗口在数组上线性移动，检查每个可能的窗口位置。

空间复杂度:

• O(1) — 如果使用固定数量的额外内存来存储当前值。
• O(k) — 如果需要存储窗口大小为 k 内的元素。

3.2 找到最大子数组和。

找到固定大小子数组的最大和

任务:

找到具有最大和的固定大小子数组 k。

解决方案:

使用滑动窗口法保持当前子数组和，并在窗口移动时更新最大和。

时间复杂度: O(n).

Python 示例代码:

def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return -1
            
    window_sum = sum(arr[:k])
    max_sum = window_sum
            
    for i in range(n - k):
        window_sum = window_sum - arr[i] + arr[i + k]
        max_sum = max(max_sum, window_sum)
            
    return max_sum
        
        

3.3 找到字符串中所有的子字符串异位词

任务:

找到字符串 s 中所有给定子字符串 p 的异位词。

解决方案:

使用滑动窗口法保持当前窗口的字符频率字典，并将其与子字符串的频率字典进行比较。

时间复杂度: O(n).

Python 示例代码:

from collections import Counter

def find_anagrams(s, p):
    p_count = Counter(p)
    s_count = Counter()
                
    result = []
    k = len(p)
                
    for i in range(len(s)):
        s_count[s[i]] += 1
        
        if i >= k:
            if s_count[s[i - k]] == 1:
                del s_count[s[i - k]]
            else:
                s_count[s[i - k]] -= 1
                            
        if s_count == p_count:
            result.append(i - k + 1)

    return result
        

3.4 找到最小子数组

找到和大于给定值的最小子数组

任务:

找到元素和大于给定值 S 的最小子数组。

解决方案:

使用滑动窗口法扩展右边界直到总和大于 S，然后移动左边界以最小化子数组长度。

时间复杂度: O(n).

Python 示例代码:

def min_subarray_len(S, arr):
    n = len(arr)
    min_len = float('inf')
    current_sum = 0
    left = 0
            
    for right in range(n):
        current_sum += arr[right]
                
        while current_sum >= S:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1
            
    return 0 if min_len == float('inf') else min_len