📚 XXY的学习笔记

滑动窗口入门

2026年2月26日
计划中
算法 滑动窗口 子数组

概念理解

滑动窗口（Sliding Window）是双指针技巧的一种应用，专门用于处理连续子数组/子字符串相关的问题。

核心思想

维护一个”窗口”（通常由左右指针定义），通过移动窗口的边界来遍历所有可能的子区间。

适用场景

  1. 子数组/子字符串的最值问题
  2. 满足特定条件的最长子数组
  3. 包含特定字符的最短子串
  4. 固定大小的窗口统计

基本模板

固定大小窗口

def fixed_window(arr, k):
    """
    固定大小为 k 的滑动窗口

    Args:
        arr: 数组
        k: 窗口大小

    Returns:
        每个窗口的结果
    """
    result = []
    window_sum = sum(arr[:k])
    result.append(window_sum)

    for i in range(k, len(arr)):
        # 移除最左边的元素，添加新元素
        window_sum = window_sum - arr[i - k] + arr[i]
        result.append(window_sum)

    return result

可变大小窗口

def variable_window(arr, condition):
    """
    可变大小的滑动窗口

    Args:
        arr: 数组
        condition: 窗口需要满足的条件

    Returns:
        满足条件的最优结果
    """
    left = 0
    result = 0

    for right in range(len(arr)):
        # 扩大窗口
        # 添加 arr[right] 到窗口

        # 当窗口不满足条件时，缩小窗口
        while not condition:
            # 移除 arr[left] 从窗口
            left += 1

        # 更新结果
        # result = max/min(result, window_size)

    return result

经典例题

1. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target，找出数组中满足其和 ≥ target 的长度最小的连续子数组。

def min_subarray_len(nums, target):
    """
    找出和 >= target 的最短子数组长度
    """
    left = 0
    window_sum = 0
    min_len = float('inf')

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

        while window_sum >= target:
            min_len = min(min_len, right - left + 1)
            window_sum -= nums[left]
            left += 1

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

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

2. 无重复字符的最长子串

def length_of_longest_substring(s):
    """
    找出不含重复字符的最长子串长度
    """
    char_set = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1

        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)

    return max_len

# 使用示例
s = "abcabcbb"
print(length_of_longest_substring(s))  # 输出: 3

学习计划

  • 理解滑动窗口的基本概念
  • 掌握固定大小窗口的实现
  • 掌握可变大小窗口的实现
  • 练习 10+ 道相关题目

相关题目