滑动窗口 · Sliding Window

一句话骨架：右指针扩张吃元素，左指针在「窗口违规」时收缩——左右指针都只走 n 步，所以 O(n)。

何时用

"连续子串 / 子数组"且需要某种约束（无重复 / 字符分布 / 长度固定 / 覆盖目标）
暴力枚举所有区间是 O(n²) 或更高，但相邻区间状态可增量更新
字符串/数组上的"覆盖"、"恰好包含"、"最多 K 种"等问句

通用模板

python

left = 0
window = {}
best = 0
for right, ch in enumerate(s):
    # 1. 把 ch 加入 window
    window[ch] = window.get(ch, 0) + 1
    # 2. 当窗口违规时收缩
    while violates(window):
        window[s[left]] -= 1
        if window[s[left]] == 0: del window[s[left]]
        left += 1
    # 3. 更新答案
    best = max(best, right - left + 1)
return best

关卡 1 · 无重复字符的最长子串

学习目标

理解"位置法"与"计数法"两种滑窗写法的差别——前者一次跳跃 O(n)，后者更通用可改 K-种限制题。

#3无重复字符的最长子串中等

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

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

子串是字符串中连续的字符序列。

示例 1

输入s = "abcabcbb"

输出3

💡 最长子串为 "abc"，长度 3

示例 2

输入s = "bbbbb"

输出1

💡 最长子串为 "b"

示例 3

输入s = "pwwkew"

输出3

💡 最长子串为 "wke"；注意 "pwke" 是子序列而非子串

约束

0 ≤ s.length ≤ 5 × 10⁴
s 由英文字母、数字、符号和空格组成

💡 思路：滑动窗口 + 哈希记位置。右指针不断扩张吞入新字符；当新字符在窗口内已出现过（last[ch] >= left）就把 left 跳到该字符上次位置 +1，跳过后窗口里再次没有重复。每步用 right - left + 1 更新答案。

✅ 完整解法

时间 O(n) · 空间 O(min(n, Σ))

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def lengthOfLongestSubstring(s: str) -> int: 2    last = {}            # 字符 -> 上次出现位置 3    left = 0 4    best = 0 5    for right, ch in enumerate(s): 6        if ch in last and last[ch] >= left: 7            left = last[ch] + 1 8        last[ch] = right 9        best = max(best, right - left + 1)10    return best

🐞 单步可视化

示例：s = "abcabcbb"

代码L4

 1def lengthOfLongestSubstring(s: str) -> int: 2    last = {}            # 字符 -> 上次出现位置 3    left = 0 4    best = 0 5    for right, ch in enumerate(s): 6        if ch in last and last[ch] >= left: 7            left = last[ch] + 1 8        last[ch] = right 9        best = max(best, right - left + 1)10    return best

数据流

best0窗口[0, -1] 长度 0

last（字符 → 上次下标）

空

1 / 34初始化 last={}, left=0, best=0

速度

🧠 理解检验

每题都对应解法的某一行或某个决策

本题最适合的算法骨架是？

last 字典里 key 和 value 的语义最该是？

 1def lengthOfLongestSubstring(s: str) -> int: 2    last = {}            # 字符 -> 上次出现位置 3    left = 0 4    best = 0 5    for right, ch in enumerate(s): 6        if ch in last and last[ch] >= left: 7            left = last[ch] + 1 8        last[ch] = right 9        best = max(best, right - left + 1)10    return best

遇到重复字符 ch 时，为什么判断条件是 last[ch] >= left 而不是 ch in last？

 1def lengthOfLongestSubstring(s: str) -> int: 2    last = {}            # 字符 -> 上次出现位置 3    left = 0 4    best = 0 5    for right, ch in enumerate(s): 6        if ch in last and last[ch] >= left: 7            left = last[ch] + 1 8        last[ch] = right 9        best = max(best, right - left + 1)10    return best

收缩 left 时为什么是 left = last[ch] + 1，而不是 left += 1？

 1def lengthOfLongestSubstring(s: str) -> int: 2    last = {}            # 字符 -> 上次出现位置 3    left = 0 4    best = 0 5    for right, ch in enumerate(s): 6        if ch in last and last[ch] >= left: 7            left = last[ch] + 1 8        last[ch] = right 9        best = max(best, right - left + 1)10    return best

last[ch] = right 这一句应该放在哪里？

 1def lengthOfLongestSubstring(s: str) -> int: 2    last = {}            # 字符 -> 上次出现位置 3    left = 0 4    best = 0 5    for right, ch in enumerate(s): 6        if ch in last and last[ch] >= left: 7            left = last[ch] + 1 8        last[ch] = right 9        best = max(best, right - left + 1)10    return best

当前窗口长度的正确表达式是？

 1def lengthOfLongestSubstring(s: str) -> int: 2    last = {}            # 字符 -> 上次出现位置 3    left = 0 4    best = 0 5    for right, ch in enumerate(s): 6        if ch in last and last[ch] >= left: 7            left = last[ch] + 1 8        last[ch] = right 9        best = max(best, right - left + 1)10    return best

left 在循环过程中是否可能减小（回退）？

时间复杂度是？

空间复杂度是？

若改用"窗口里维护字符计数 + while 收缩"的写法，与位置法的区别？

空串 s = "" 时该解法的行为？

题目问"最长子串"，下面哪一项与本题无关？

关卡 2 · 找到字符串中所有字母异位词

学习目标

学会定长滑窗：窗口大小恒为 len(p)，进新出旧同步更新两张计数表，相等时记录起点。这是滑窗里最规整的一种写法。

#438找到字符串中所有字母异位词中等

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词指由相同字母重排列形成的字符串（包括相同的字符串本身）。

示例 1

输入s = "cbaebabacd", p = "abc"

输出[0, 6]

💡 起始 0 的子串 "cba"、起始 6 的子串 "bac" 都是 "abc" 的异位词

示例 2

输入s = "abab", p = "ab"

输出[0, 1, 2]

约束

1 ≤ s.length, p.length ≤ 3 × 10⁴
s 和 p 仅包含小写字母

💡 思路：固定长度滑窗。窗口长度恒为 len(p)。维护两张 26 长度的字符计数表 need / have：右进左出（进窗口时 have[ch]+=1，超长时 have[s[left]]-=1），每步比较两表是否相等；相等就把窗口起点 right - m + 1 入答案。

✅ 完整解法

时间 O(n × Σ) · 空间 O(Σ)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def findAnagrams(s: str, p: str) -> list[int]: 2    n, m = len(s), len(p) 3    if n < m: 4        return [] 5    need = [0] * 26 6    have = [0] * 26 7    for ch in p: 8        need[ord(ch) - 97] += 1 9    res = []10    for right in range(n):11        have[ord(s[right]) - 97] += 112        if right >= m:13            have[ord(s[right - m]) - 97] -= 114        if have == need:15            res.append(right - m + 1)16    return res

🐞 单步可视化

示例：s = "cbaebabacd", p = "abc"

代码L2

 1def findAnagrams(s: str, p: str) -> list[int]: 2    n, m = len(s), len(p) 3    if n < m: 4        return [] 5    need = [0] * 26 6    have = [0] * 26 7    for ch in p: 8        need[ord(ch) - 97] += 1 9    res = []10    for right in range(n):11        have[ord(s[right]) - 97] += 112        if right >= m:13            have[ord(s[right - m]) - 97] -= 114        if have == need:15            res.append(right - m + 1)16    return res

数据流

m3res[]

need（p 的字符计数，仅显示非零）

have（窗口字符计数，仅显示非零）

空

1 / 41n=10, m=3，先校验 n < m

速度

🧠 理解检验

每题都对应解法的某一行或某个决策

本题最适合的窗口形态是？

need / have 用 26 长度数组而非 dict 的好处是？

 1def findAnagrams(s: str, p: str) -> list[int]: 2    n, m = len(s), len(p) 3    if n < m: 4        return [] 5    need = [0] * 26 6    have = [0] * 26 7    for ch in p: 8        need[ord(ch) - 97] += 1 9    res = []10    for right in range(n):11        have[ord(s[right]) - 97] += 112        if right >= m:13            have[ord(s[right - m]) - 97] -= 114        if have == need:15            res.append(right - m + 1)16    return res

ord(ch) - 97 这个写法的含义？

判断"窗口已满"的条件应该是？

 1def findAnagrams(s: str, p: str) -> list[int]: 2    n, m = len(s), len(p) 3    if n < m: 4        return [] 5    need = [0] * 26 6    have = [0] * 26 7    for ch in p: 8        need[ord(ch) - 97] += 1 9    res = []10    for right in range(n):11        have[ord(s[right]) - 97] += 112        if right >= m:13            have[ord(s[right - m]) - 97] -= 114        if have == need:15            res.append(right - m + 1)16    return res

弹出旧字符时正确的索引是？

 1def findAnagrams(s: str, p: str) -> list[int]: 2    n, m = len(s), len(p) 3    if n < m: 4        return [] 5    need = [0] * 26 6    have = [0] * 26 7    for ch in p: 8        need[ord(ch) - 97] += 1 9    res = []10    for right in range(n):11        have[ord(s[right]) - 97] += 112        if right >= m:13            have[ord(s[right - m]) - 97] -= 114        if have == need:15            res.append(right - m + 1)16    return res

何时记录答案？

 1def findAnagrams(s: str, p: str) -> list[int]: 2    n, m = len(s), len(p) 3    if n < m: 4        return [] 5    need = [0] * 26 6    have = [0] * 26 7    for ch in p: 8        need[ord(ch) - 97] += 1 9    res = []10    for right in range(n):11        have[ord(s[right]) - 97] += 112        if right >= m:13            have[ord(s[right - m]) - 97] -= 114        if have == need:15            res.append(right - m + 1)16    return res

匹配窗口的起点应该是？

 1def findAnagrams(s: str, p: str) -> list[int]: 2    n, m = len(s), len(p) 3    if n < m: 4        return [] 5    need = [0] * 26 6    have = [0] * 26 7    for ch in p: 8        need[ord(ch) - 97] += 1 9    res = []10    for right in range(n):11        have[ord(s[right]) - 97] += 112        if right >= m:13            have[ord(s[right - m]) - 97] -= 114        if have == need:15            res.append(right - m + 1)16    return res

若不预判 if n < m: return []，会发生什么？

 1def findAnagrams(s: str, p: str) -> list[int]: 2    n, m = len(s), len(p) 3    if n < m: 4        return [] 5    need = [0] * 26 6    have = [0] * 26 7    for ch in p: 8        need[ord(ch) - 97] += 1 9    res = []10    for right in range(n):11        have[ord(s[right]) - 97] += 112        if right >= m:13            have[ord(s[right - m]) - 97] -= 114        if have == need:15            res.append(right - m + 1)16    return res

时间复杂度是？

空间复杂度是？

能否优化为"每步不全比较 26 个，只维护一个匹配数 matched"？

若题目改成"包含 p 的某种排列作为子串"（即 LeetCode 567 字符串的排列），写法变化？

关卡 3 · 最小覆盖子串

学习目标

掌握变长滑窗的精髓：用 formed/required 两个量把"是否覆盖"压成 O(1) 判断，配合"扩张外循环 + 收缩内循环"双层结构。这是滑窗 hard 题的统一范式。

#76最小覆盖子串困难

♥♥♥♥♥+0 XP🔥 0

0 / 13

📝 题目

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

注意：
- 对于 t 中重复字符，我们寻找的子串中该字符数量必须不少于 t 中该字符数量。
- 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1

输入s = "ADOBECODEBANC", t = "ABC"

输出"BANC"

💡 "BANC" 是唯一覆盖 A、B、C 的最小子串

示例 2

输入s = "a", t = "a"

输出"a"

示例 3

输入s = "a", t = "aa"

输出""

💡 t 要两个 a，s 只有一个，无解

约束

m == s.length, n == t.length
1 ≤ m, n ≤ 10⁵
s 和 t 由英文字母组成

💡 思路：变长滑窗。用 need 记录 t 的字符需求；窗口里 have 计数 + formed 跟踪"已经凑齐数量的字符种数"。右指针扩张，formed == required 时进入收缩内循环：每弹出一个左字符，更新答案 + 必要时降低 formed 退出收缩。formed 这个量把"是否覆盖"压成 O(1) 判断，避免每步比较两张表。

✅ 完整解法

时间 O(m + n) · 空间 O(Σ)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def minWindow(s: str, t: str) -> str: 2    if not s or not t or len(s) < len(t): 3        return 「」 4    need = {} 5    for ch in t: 6        need[ch] = need.get(ch, 0) + 1 7    required = len(need)        # 不同字符种类数 8    have = {} 9    formed = 0                  # 已经「凑齐数量」的字符种数10    left = 011    best_len = float(「inf」)12    best_l = 013    for right, ch in enumerate(s):14        have[ch] = have.get(ch, 0) + 115        if ch in need and have[ch] == need[ch]:16            formed += 117        while formed == required:18            if right - left + 1 < best_len:19                best_len = right - left + 120                best_l = left21            lc = s[left]22            have[lc] -= 123            if lc in need and have[lc] < need[lc]:24                formed -= 125            left += 126    return 「」 if best_len == float(「inf」) else s[best_l: best_l + best_len]

🐞 单步可视化

示例：s = "ADOBECODEBANC", t = "ABC"

代码L2

 1def minWindow(s: str, t: str) -> str: 2    if not s or not t or len(s) < len(t): 3        return 「」 4    need = {} 5    for ch in t: 6        need[ch] = need.get(ch, 0) + 1 7    required = len(need)        # 不同字符种类数 8    have = {} 9    formed = 0                  # 已经「凑齐数量」的字符种数10    left = 011    best_len = float(「inf」)12    best_l = 013    for right, ch in enumerate(s):14        have[ch] = have.get(ch, 0) + 115        if ch in need and have[ch] == need[ch]:16            formed += 117        while formed == required:18            if right - left + 1 < best_len:19                best_len = right - left + 120                best_l = left21            lc = s[left]22            have[lc] -= 123            if lc in need and have[lc] < need[lc]:24                formed -= 125            left += 126    return 「」 if best_len == float(「inf」) else s[best_l: best_l + best_len]

数据流

required0formed0best_len∞best_l0

need / have（每对：need → have）

空

1 / 92校验：s.length=13, t.length=3

速度

🧠 理解检验

每题都对应解法的某一行或某个决策

本题与"找异位词"相比，关键的形态差别？

required = len(need) 的语义是？

 1def minWindow(s: str, t: str) -> str: 2    if not s or not t or len(s) < len(t): 3        return 「」 4    need = {} 5    for ch in t: 6        need[ch] = need.get(ch, 0) + 1 7    required = len(need)        # 不同字符种类数 8    have = {} 9    formed = 0                  # 已经「凑齐数量」的字符种数10    left = 011    best_len = float(「inf」)12    best_l = 013    for right, ch in enumerate(s):14        have[ch] = have.get(ch, 0) + 115        if ch in need and have[ch] == need[ch]:16            formed += 117        while formed == required:18            if right - left + 1 < best_len:19                best_len = right - left + 120                best_l = left21            lc = s[left]22            have[lc] -= 123            if lc in need and have[lc] < need[lc]:24                formed -= 125            left += 126    return 「」 if best_len == float(「inf」) else s[best_l: best_l + best_len]

formed += 1 应在何时触发？

 1def minWindow(s: str, t: str) -> str: 2    if not s or not t or len(s) < len(t): 3        return 「」 4    need = {} 5    for ch in t: 6        need[ch] = need.get(ch, 0) + 1 7    required = len(need)        # 不同字符种类数 8    have = {} 9    formed = 0                  # 已经「凑齐数量」的字符种数10    left = 011    best_len = float(「inf」)12    best_l = 013    for right, ch in enumerate(s):14        have[ch] = have.get(ch, 0) + 115        if ch in need and have[ch] == need[ch]:16            formed += 117        while formed == required:18            if right - left + 1 < best_len:19                best_len = right - left + 120                best_l = left21            lc = s[left]22            have[lc] -= 123            if lc in need and have[lc] < need[lc]:24                formed -= 125            left += 126    return 「」 if best_len == float(「inf」) else s[best_l: best_l + best_len]

何时应该尝试收缩 left？

 1def minWindow(s: str, t: str) -> str: 2    if not s or not t or len(s) < len(t): 3        return 「」 4    need = {} 5    for ch in t: 6        need[ch] = need.get(ch, 0) + 1 7    required = len(need)        # 不同字符种类数 8    have = {} 9    formed = 0                  # 已经「凑齐数量」的字符种数10    left = 011    best_len = float(「inf」)12    best_l = 013    for right, ch in enumerate(s):14        have[ch] = have.get(ch, 0) + 115        if ch in need and have[ch] == need[ch]:16            formed += 117        while formed == required:18            if right - left + 1 < best_len:19                best_len = right - left + 120                best_l = left21            lc = s[left]22            have[lc] -= 123            if lc in need and have[lc] < need[lc]:24                formed -= 125            left += 126    return 「」 if best_len == float(「inf」) else s[best_l: best_l + best_len]

收缩时 formed -= 1 应在什么条件下触发？

 1def minWindow(s: str, t: str) -> str: 2    if not s or not t or len(s) < len(t): 3        return 「」 4    need = {} 5    for ch in t: 6        need[ch] = need.get(ch, 0) + 1 7    required = len(need)        # 不同字符种类数 8    have = {} 9    formed = 0                  # 已经「凑齐数量」的字符种数10    left = 011    best_len = float(「inf」)12    best_l = 013    for right, ch in enumerate(s):14        have[ch] = have.get(ch, 0) + 115        if ch in need and have[ch] == need[ch]:16            formed += 117        while formed == required:18            if right - left + 1 < best_len:19                best_len = right - left + 120                best_l = left21            lc = s[left]22            have[lc] -= 123            if lc in need and have[lc] < need[lc]:24                formed -= 125            left += 126    return 「」 if best_len == float(「inf」) else s[best_l: best_l + best_len]

更新答案应该在收缩 left 之前还是之后？

 1def minWindow(s: str, t: str) -> str: 2    if not s or not t or len(s) < len(t): 3        return 「」 4    need = {} 5    for ch in t: 6        need[ch] = need.get(ch, 0) + 1 7    required = len(need)        # 不同字符种类数 8    have = {} 9    formed = 0                  # 已经「凑齐数量」的字符种数10    left = 011    best_len = float(「inf」)12    best_l = 013    for right, ch in enumerate(s):14        have[ch] = have.get(ch, 0) + 115        if ch in need and have[ch] == need[ch]:16            formed += 117        while formed == required:18            if right - left + 1 < best_len:19                best_len = right - left + 120                best_l = left21            lc = s[left]22            have[lc] -= 123            if lc in need and have[lc] < need[lc]:24                formed -= 125            left += 126    return 「」 if best_len == float(「inf」) else s[best_l: best_l + best_len]

为什么 best_len 用 float("inf") 初始化？

 1def minWindow(s: str, t: str) -> str: 2    if not s or not t or len(s) < len(t): 3        return 「」 4    need = {} 5    for ch in t: 6        need[ch] = need.get(ch, 0) + 1 7    required = len(need)        # 不同字符种类数 8    have = {} 9    formed = 0                  # 已经「凑齐数量」的字符种数10    left = 011    best_len = float(「inf」)12    best_l = 013    for right, ch in enumerate(s):14        have[ch] = have.get(ch, 0) + 115        if ch in need and have[ch] == need[ch]:16            formed += 117        while formed == required:18            if right - left + 1 < best_len:19                best_len = right - left + 120                best_l = left21            lc = s[left]22            have[lc] -= 123            if lc in need and have[lc] < need[lc]:24                formed -= 125            left += 126    return 「」 if best_len == float(「inf」) else s[best_l: best_l + best_len]

have 是否需要排除 t 之外的字符？例如 s 里的"杂质"

为什么 t 中有重复字符（如 t = "aab"）也能被这套写法正确处理？

时间复杂度是？

空间复杂度是？

如果删除 formed 这个量，改成"每步比较 have 是否覆盖 need"，会怎样？

收尾返回时为何要判断 best_len == float("inf")？

 1def minWindow(s: str, t: str) -> str: 2    if not s or not t or len(s) < len(t): 3        return 「」 4    need = {} 5    for ch in t: 6        need[ch] = need.get(ch, 0) + 1 7    required = len(need)        # 不同字符种类数 8    have = {} 9    formed = 0                  # 已经「凑齐数量」的字符种数10    left = 011    best_len = float(「inf」)12    best_l = 013    for right, ch in enumerate(s):14        have[ch] = have.get(ch, 0) + 115        if ch in need and have[ch] == need[ch]:16            formed += 117        while formed == required:18            if right - left + 1 < best_len:19                best_len = right - left + 120                best_l = left21            lc = s[left]22            have[lc] -= 123            if lc in need and have[lc] < need[lc]:24                formed -= 125            left += 126    return 「」 if best_len == float(「inf」) else s[best_l: best_l + best_len]

同 pattern 索引（hot100 同类题）

题号	题名	难度	关键变形
239	滑动窗口最大值	困难	单调递减双端队列维护窗口最大值
567	字符串的排列	中等	与 438 双胞胎，固定长度滑窗判窗口字符分布 == p
209	长度最小的子数组	中等	数值版变长滑窗，sum ≥ target 时收缩 left
424	替换后的最长重复字符	中等	维护"窗口长度 - 最高频字符次数 ≤ k"作为不变式

面试常踩

变长 vs 定长——开题先判：窗口长度由谁决定？长度未知就是变长，要"扩张外 + 收缩内"双循环；长度等于某给定值就是定长，单循环 + if right >= m: 弹左。
位置法 vs 计数法——位置法（last[ch] = right）只解"无重复"类，常数小；计数法可解"最多 K 种"等通用变形，常数稍大。看题选写法。
have == need 的常数代价——438 用定长 26 数组比较是 O(Σ)，Σ 视为常数；如果换成 dict 比较，常数会显著放大。这是数据结构选择影响速度的典型例子。
formed 的 invariant 维护——只有"由不达标变为达标"那一步 +1，"由达标变为不达标"那一步 -1。多写几次最小覆盖子串就能形成肌肉记忆。

滑动窗口 · Sliding Window ​

何时用 ​

通用模板 ​

关卡 1 · 无重复字符的最长子串 ​

📝 题目

✅ 完整解法

🧠 理解检验

关卡 2 · 找到字符串中所有字母异位词 ​

📝 题目

✅ 完整解法

🧠 理解检验

关卡 3 · 最小覆盖子串 ​

📝 题目

✅ 完整解法

🧠 理解检验

同 pattern 索引（hot100 同类题） ​

面试常踩 ​

滑动窗口 · Sliding Window

何时用

通用模板

关卡 1 · 无重复字符的最长子串

关卡 2 · 找到字符串中所有字母异位词

关卡 3 · 最小覆盖子串

同 pattern 索引（hot100 同类题）

面试常踩