30 秒速览

  • 什么时候用：连续子数组/子串问题、区间内维护状态
  • 核心思想：用双指针维护一个窗口，动态扩张/收缩
  • 时间复杂度：O(n)
  • 空间复杂度：O(k)，k 是窗口内字符种类数

一、直觉建立

火车窗外的风景

想象你在看火车窗外的风景：

火车行驶时，窗户框住的风景在变化。你的任务是：找到最美的一段风景（满足某个条件的最优子串/子数组）。

关键：你不需要每次都从头看到尾，只需要随着窗口滑动，更新窗口内的状态。

滑动窗口的本质

滑动窗口 = 双指针 + 区间状态维护

子数组/子串问题：
- 暴力: 枚举所有 (i, j)，O(n²)
- 滑动窗口: 利用单调性，O(n)

当右指针扩展使得窗口不满足条件时，收缩左指针
当左指针收缩使得窗口重新满足条件时，更新答案

两类滑动窗口问题

类型特点收缩时机更新时机
求最长窗口越大越好不满足条件时收缩收缩后更新
求最短窗口越小越好满足条件时收缩收缩时更新

二、通用模板

def sliding_window(s: str) -> int:
    """滑动窗口通用模板"""
    from collections import defaultdict

    window = defaultdict(int)  # 窗口内的状态
    left = 0
    result = 0  # 或 float('inf') 求最短

    for right in range(len(s)):
        # 1. 扩大窗口：将 s[right] 加入窗口
        window[s[right]] += 1

        # 2. 收缩窗口（根据题目条件）
        while need_shrink(window):  # 或 while valid(window) 求最短
            window[s[left]] -= 1
            if window[s[left]] == 0:
                del window[s[left]]
            left += 1

        # 3. 更新结果（位置根据题目调整）
        result = max(result, right - left + 1)  # 求最长

    return result

三、典型例题

例题 1：LC 3. 无重复字符的最长子串

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

示例：

输入: s = "abcabcbb"
输出: 3 （"abc"）

思路分析

类型：求最长
条件：窗口内无重复字符
收缩时机：窗口内有重复字符时收缩
更新时机：收缩后更新

s = "abcabcbb"

right=0 (a): window={a:1}, 无重复, max=1
right=1 (b): window={a:1,b:1}, 无重复, max=2
right=2 (c): window={a:1,b:1,c:1}, 无重复, max=3
right=3 (a): window={a:2,b:1,c:1}, 有重复！
  收缩: left=1, window={a:1,b:1,c:1}, 无重复, max=3
right=4 (b): window={a:1,b:2,c:1}, 有重复！
  收缩: left=2, window={a:1,b:1,c:1}, 无重复, max=3
...

代码

def lengthOfLongestSubstring(s: str) -> int:
    window = set()  # 用 set 判断重复更简洁
    left = 0
    max_len = 0

    for right in range(len(s)):
        # 如果有重复，收缩窗口
        while s[right] in window:
            window.remove(s[left])
            left += 1

        # 加入窗口
        window.add(s[right])

        # 更新结果
        max_len = max(max_len, right - left + 1)

    return max_len

优化版本

记录字符最后出现的位置，直接跳过：

def lengthOfLongestSubstring(s: str) -> int:
    char_index = {}  # 字符 -> 最后出现的位置
    left = 0
    max_len = 0

    for right, c in enumerate(s):
        if c in char_index and char_index[c] >= left:
            left = char_index[c] + 1
        char_index[c] = right
        max_len = max(max_len, right - left + 1)

    return max_len

复杂度：时间 O(n)，空间 O(min(m, n))，m 是字符集大小

例题 2：LC 209. 长度最小的子数组

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

示例：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2 （[4,3]）

思路分析

类型：求最短
条件：窗口和 >= target
收缩时机：窗口满足条件时收缩（因为要找最短）
更新时机：收缩时更新

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

right=0: sum=2 < 7
right=1: sum=5 < 7
right=2: sum=6 < 7
right=3: sum=8 >= 7, 更新 min_len=4
  收缩: sum=6 < 7, left=1
right=4: sum=10 >= 7, 更新 min_len=4
  收缩: sum=7 >= 7, 更新 min_len=3
  收缩: sum=6 < 7, left=3
right=5: sum=9 >= 7, 更新 min_len=3
  收缩: sum=7 >= 7, 更新 min_len=2
  收缩: sum=3 < 7, left=5

最终: min_len=2

代码

def minSubArrayLen(target: int, nums: list[int]) -> int:
    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

复杂度：时间 O(n)，空间 O(1)

例题 3：LC 76. 最小覆盖子串（Hard）

题目：给你一个字符串 s 和一个字符串 t，返回 s 中涵盖 t 所有字符的最小子串。如果不存在返回空字符串。

示例：

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

思路分析

类型：求最短
条件：窗口包含 t 的所有字符
收缩时机：窗口满足条件时收缩
更新时机：收缩时更新

关键：如何判断"包含 t 的所有字符"？
- 维护 need 计数器，记录 t 中每个字符需要的个数
- 维护 window 计数器，记录窗口中每个字符的个数
- 当 window[c] == need[c] 时，一个字符"满足"了
- 当所有字符都"满足"时，窗口合法

代码

from collections import Counter

def minWindow(s: str, t: str) -> str:
    need = Counter(t)  # t 中每个字符需要的个数
    window = {}        # 窗口中每个字符的个数

    have = 0           # 已满足的字符种类数
    need_cnt = len(need)  # 需要满足的字符种类数

    left = 0
    result = ""
    min_len = float('inf')

    for right in range(len(s)):
        # 扩大窗口
        c = s[right]
        window[c] = window.get(c, 0) + 1

        # 如果这个字符刚好满足需求
        if c in need and window[c] == need[c]:
            have += 1

        # 满足条件时收缩
        while have == need_cnt:
            # 更新答案
            if right - left + 1 < min_len:
                min_len = right - left + 1
                result = s[left:right + 1]

            # 收缩窗口
            d = s[left]
            if d in need and window[d] == need[d]:
                have -= 1
            window[d] -= 1
            left += 1

    return result

复杂度：时间 O(n)，空间 O(m)，m 是字符集大小

例题 4：LC 438. 找到字符串中所有字母异位词

题目：给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。

示例：

输入: s = "cbaebabacd", p = "abc"
输出: [0, 6]

思路分析

这是固定窗口的滑动窗口问题：窗口大小固定为 len(p)。

代码

from collections import Counter

def findAnagrams(s: str, p: str) -> list[int]:
    if len(s) < len(p):
        return []

    need = Counter(p)
    window = Counter()
    result = []

    for i in range(len(s)):
        # 加入右边的字符
        window[s[i]] += 1

        # 如果窗口超过 p 的长度，移除左边的字符
        if i >= len(p):
            left_char = s[i - len(p)]
            window[left_char] -= 1
            if window[left_char] == 0:
                del window[left_char]

        # 如果窗口和 need 相等，找到一个异位词
        if window == need:
            result.append(i - len(p) + 1)

    return result

复杂度：时间 O(n)，空间 O(m)

例题 5：LC 904. 水果成篮

题目：你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。你有两个篮子，每个篮子只能装一种水果，但每种水果的数量不限。从任意一棵树开始，你必须从每棵树（包括起始树）恰好采摘一个水果。采摘的水果应当符合篮子中的水果品种。一旦你走到一棵树，树上的水果类型与你两个篮子中的水果类型都不相同，就必须停止。求最多能摘多少个水果。

示例：

输入：fruits = [1,2,1,2,3,2,2]
输出：4 （采摘 [2,3,2,2]）

思路分析

本质上就是：最多包含两种不同元素的最长连续子数组。

类型：求最长
条件：窗口内元素种类 <= 2
收缩时机：元素种类 > 2 时收缩
更新时机：收缩后更新

代码

def totalFruit(fruits: list[int]) -> int:
    from collections import defaultdict

    window = defaultdict(int)
    left = 0
    max_len = 0

    for right in range(len(fruits)):
        window[fruits[right]] += 1

        # 种类超过 2，收缩窗口
        while len(window) > 2:
            window[fruits[left]] -= 1
            if window[fruits[left]] == 0:
                del window[fruits[left]]
            left += 1

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

    return max_len

复杂度：时间 O(n)，空间 O(1)（最多 3 种）

四、求最长 vs 求最短

求最长

for right in range(len(s)):
    # 扩大窗口
    window.add(s[right])

    # 不满足条件时收缩
    while not valid(window):
        window.remove(s[left])
        left += 1

    # 收缩后更新（此时窗口一定满足条件）
    result = max(result, right - left + 1)

求最短

for right in range(len(s)):
    # 扩大窗口
    window.add(s[right])

    # 满足条件时收缩
    while valid(window):
        # 收缩时更新（此时窗口满足条件，可能更短）
        result = min(result, right - left + 1)
        window.remove(s[left])
        left += 1

五、常见错误与陷阱

错误 1：混淆求最长和求最短

# 求最长：在收缩后更新
while not valid():
    shrink()
result = max(result, ...)  # 收缩后

# 求最短：在收缩时更新
while valid():
    result = min(result, ...)  # 收缩前
    shrink()

错误 2：忘记在收缩时更新状态

# 错误：只移动指针，不更新窗口状态
while need_shrink():
    left += 1  # ✗ 忘记从 window 中移除

# 正确
while need_shrink():
    window[s[left]] -= 1
    left += 1

错误 3：不知道何时能用滑动窗口

滑动窗口需要单调性：窗口扩大时，某个指标单调变化。

不能用滑动窗口的情况：
- 和为 K 的子数组（可能有负数，窗口扩大时和不一定增加）
- 需要回溯的情况

可以用滑动窗口的情况：
- 无重复字符（窗口扩大，重复只可能增加）
- 正数数组的和（窗口扩大，和一定增加）

六、复盘清单

触发信号

  • 连续子数组/子串问题
  • 需要找满足条件的最长/最短区间
  • 区间内维护某种状态（计数、和等）
  • 问题具有单调性

边界条件

  • 空字符串
  • 单字符
  • 所有字符相同
  • 无解情况（返回 0 或空串）

常见错误

  • 混淆求最长和求最短的更新时机
  • 收缩时忘记更新窗口状态
  • 循环条件错误
  • 不满足单调性时强行用滑动窗口

七、题目清单

基础题

题号题目难度类型
3无重复字符的最长子串Medium求最长
209长度最小的子数组Medium求最短
219存在重复元素 IIEasy固定窗口
438找到所有字母异位词Medium固定窗口

进阶题

题号题目难度类型
76最小覆盖子串Hard求最短
567字符串的排列Medium固定窗口
904水果成篮Medium求最长
424替换后的最长重复字符Medium求最长
992K 个不同整数的子数组Hard求最长