Python系列 - 滑动窗口

Python - 这篇文章属于一个选集。

§ 2: 本文

1. 介绍
#

滑动窗口（Sliding Window）是一种常用于数组或字符串的算法技巧，它通过在数组或字符串上维护一个窗口，逐步滑动以检查和处理窗口内的元素，从而达到优化时间复杂度的效果。滑动窗口通常用于解决子数组或子字符串的问题，比如最大或最小子数组和、满足某种条件的子数组数量等。

1.1. 核心思想
#

维护一个窗口，初始状态为空。
不断扩展窗口的右边界，直到满足某种条件。
在满足条件后，可以选择收缩窗口的左边界，以找到符合条件的最优解或继续寻找其他解。
重复上述步骤，直到整个数组或字符串被遍历完毕。

2. 滑动窗口的类型
#

2.1. 固定大小的滑动窗口
#

窗口的大小是固定的，主要用于处理固定大小子数组或子字符串的问题。

示例1：

找到长度为k的子数组的最大和。

def max_sum_subarray(nums, k):
    if len(nums) < k:
        return 0

    max_sum = current_sum = sum(nums[:k])
    for i in range(k, len(nums)):
        current_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, current_sum)

    return max_sum

# 示例调用
nums = [1, 4, 2, 10, 23, 3, 1, 0, 20]
k = 4
print(max_sum_subarray(nums, k))  # 输出 39

示例2：

找到字符串中所有字母异位词
- 给定一个字符串s和一个非空字符串p，找到s中所有是p字母异位词的子串，返回这些子串的起始索引。

from collections import Counter

def find_anagrams(s, p):
    result = []
    p_count = Counter(p)
    s_count = Counter()

    left = 0
    for right in range(len(s)):
        s_count[s[right]] += 1

        while right - left + 1 > len(p):
            if s_count[s[left]] == 1:
                del s_count[s[left]]
            else:
                s_count[s[left]] -= 1
            left += 1

        if s_count == p_count:
            result.append(left)

    return result

# 示例调用
s = "cbaebabacd"
p = "abc"
print(find_anagrams(s, p))  # 输出 [0, 6]

2.2. 可变大小的滑动窗口
#

窗口的大小不固定，根据条件动态调整窗口的大小，主要用于处理可变大小子数组或子字符串的问题。

示列1

找到和为目标值的最短子数组长度（只考虑正整数的情况）。

def min_subarray_len(nums, target):
    left = 0
    current_sum = 0
    min_length = float('inf')

    for right in range(len(nums)):
        current_sum += nums[right]

        while current_sum >= target:
            if current_sum == target:
                min_length = min(min_length, right - left + 1)
            current_sum -= nums[left]
            left += 1

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

# 示例调用
nums = [2, 3, 1, 2, 4, 3]
target = 7
print(min_subarray_len(nums, target))  # 输出 2

示例2

找到数组中和为目标值的最长子数组（只考虑正整数的情况）。
- 给定一个整数数组和一个目标值，找到和为目标值的最长子数组的长度。

def longest_subarray_with_sum(nums, target):
    left = 0
    current_sum = 0
    max_length = 0

    for right in range(len(nums)):
        current_sum += nums[right]

        while current_sum > target and left <= right:
            current_sum -= nums[left]
            left += 1

        if current_sum == target:
            max_length = max(max_length, right - left + 1)

    return max_length


# 示例调用
nums = [1, 1, 1, 1, 5, 1, 2, 2, 4]
target = 4
print(longest_subarray_with_sum(nums, target))    # 输出 4

示例2 - 拓展

找到数组中和为目标值的最长子数组（包括负数的情况）
- 应使用前缀和及哈希表的方法，而非滑动窗口。
- 滑动窗口适用于固定或连续调整的窗口大小，但在包含负数时，它无法保证和的单调性，因此不适合这个问题。

def longest_subarray_with_sum(nums, target):
    prefix_sum_indices = {}
    current_sum = 0
    max_length = 0

    for i in range(len(nums)):
        current_sum += nums[i]

        # 如果当前前缀和等于目标值，则更新最长子数组长度
        if current_sum == target:
            max_length = i + 1

        # 如果存在前缀和 current_sum - target，则更新最长子数组长度
        if (current_sum - target) in prefix_sum_indices:
            max_length = max(max_length,
                             i - prefix_sum_indices[current_sum - target])

        # 如果当前前缀和不在哈希表中，则记录其索引
        if current_sum not in prefix_sum_indices:
            prefix_sum_indices[current_sum] = i

    return max_length

# 示例调用
nums = [1, -1, 5, -2, 3]
target = 3
print(longest_subarray_with_sum(nums, target))  # 输出 4

nums = [-2, -1, 2, 1]
target = 1
print(longest_subarray_with_sum(nums, target))  # 输出 2