438. 找到字符串中所有字母异位词 (Medium)

专题归类： 02-双指针与滑动窗口 · 01-哈希表 LeetCode 链接： https://leetcode.cn/problems/find-all-anagrams-in-a-string/

---

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

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

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

示例：

输入: s = "cbaebabacd", p = "abc"
输出: [0, 6]
解释:
起始索引等于 0 的子串是 "cba"，它是 "abc" 的异位词
起始索引等于 6 的子串是 "bac"，它是 "abc" 的异位词

补充说明：

• 1 <= s.length, p.length <= 3 * 10^4
• s 和 p 仅包含小写英文字母

---

题目详细分析

数据范围含义：

• 长度最大 3×10^4，O(n × m) 的暴力法不可行（每个位置比较两个长度为 m 的字符串会到 9×10
• 仅包含小写英文字母（26 个），这个限制非常关键——我们可以用固定长度 26 的数组来计数，比较数组是否相等只需 O(26) = O(1)。
• 注意 p 可能比 s 长，此时直接返回空列表。

核心概念：

• 异位词：字母相同且每个字母出现次数相同。比较两个字符串是否为异位词，本质是比较它们的”字符计数”是否相同。
• 定长滑动窗口：窗口大小固定为 len(p)，每次整体滑动一步。这比不定长窗口更简单——左右指针同时移动。

边界条件：

• len(p) > len(s)：直接返回 []。
• p 长度为 1：每个字符本身都是一个长度为 1 的异位词，返回所有索引。
• s 和 p 完全相同：返回 [0]。

隐藏条件：

• 题目限定了”仅包含小写英文字母”，这是非常重要的提示——暗示你可以用计数数组而非哈希表。
• 固定长度窗口有两种实现方式：维护两个数组比较，或用滑动窗口 + 差量变量（diff）追踪差异。

---

小白版直白理解

想象你在玩一个”找单词”游戏。你有一个短单词（比如 “abc”），要在长字符串里找到所有”字母相同但顺序可能不同”的子串。

比如长串是 “cbaebabacd”，你要找 “abc” 的变体：

• “cba” — c、b、a 都有，和 “abc” 用的字母一样！找到了，位置 0。
• “baeba” — 这串太长，不行。我们要找的是和 “abc” 一样长的子串。
• “bac” — b、a、c 都有！找到了，位置 6。

笨办法： 从每个位置开始，截取和 p 一样长的子串，然后排序比较两个字符串是否相同。每个子串排序要 O(k log k)，很慢。

聪明办法（滑动窗口 + 计数数组）： 你做一个 26 格的”字母计数器”，先数一下 p 中有哪些字母各多少个。然后拿着同样大小的计数器，在长串上滑动窗口——每往右走一步，新来的字母加一，离开窗口的字母减一。每次滑动后比较两个计数器是否相同。

因为每次只加减两个字母，不需要重新数整个窗口，所以非常快！

---

解题思路

思路一：固定长度滑动窗口 + 计数数组（推荐）

核心想法： 初始化 cnt_p 统计 p 中每个字母出现次数。用同样大小的 cnt_s 统计 s 中当前窗口内的字母，窗口长度固定为 len(p)。每次窗口整体右移一步，更新 cnt_s（新字符 +1，离开的字符 -1），然后比较两个数组是否相等。

关键洞察： 固定长度窗口的”滑动”意味着每次左指针和右指针各移动一次，窗口大小不变。这比不定长窗口简单——不需要 while 循环来调整大小。

def findAnagrams(s, p):
    """
    固定长度滑动窗口 + 计数数组
    比较窗口内的字符计数与 p 的字符计数是否一致
    
    步骤：
    1. 统计 p 的字符计数
    2. 遍历 s，维护同样长度的窗口计数
    3. 每次滑动后比较两个计数数组
    """
    if len(p) > len(s):
        return []
    
    cnt_p = [0] * 26
    cnt_s = [0] * 26
    
    # 统计 p 中每个字符的出现次数
    for ch in p:
        cnt_p[ord(ch) - 97] += 1
    
    res = []
    for i, ch in enumerate(s):
        # 加入当前字符
        cnt_s[ord(ch) - 97] += 1
        
        # 移除离开窗口的字符
        if i >= len(p):
            cnt_s[ord(s[i - len(p)]) - 97] -= 1
        
        # 比较两个计数数组
        if cnt_s == cnt_p:
            res.append(i - len(p) + 1)
    
    return res

思路二：滑动窗口 + 差异变量（优化）

核心想法： 不直接比较两个数组（每次 O(26)），而是用一个变量 diff 追踪窗口计数与目标计数的不同字符数量。当 diff == 0 时，说明找到了一个异位词。

关键洞察： 滑动窗口每次只增减一个字符，实际上只有两个字符的计数发生变化。我们可以只更新 diff 来反映变化，而不用每次都完整比较 26 个字符。

def findAnagrams_optimized(s, p):
    """
    滑动窗口 + 差异变量优化
    diff 记录计数不同的字符种类数
    """
    if len(p) > len(s):
        return []
    
    # 用一个数组表示「窗口计数 - 目标计数」的差值
    count = [0] * 26
    for ch in p:
        count[ord(ch) - 97] -= 1  # 先减去目标
    
    res = []
    diff = 0  # 不为 0 的字符种类数
    for i in range(26):
        if count[i] != 0:
            diff += 1
    
    for i, ch in enumerate(s):
        idx = ord(ch) - 97
        # 加入前，count[idx] 的值决定了 diff 的变化
        if count[idx] == 0:
            diff += 1  # 即将变成非 0
        elif count[idx] == -1:
            diff -= 1  # 即将变成 0
        count[idx] += 1  # 加入窗口
        
        # 移除离开窗口的字符
        if i >= len(p):
            idx_out = ord(s[i - len(p)]) - 97
            if count[idx_out] == 0:
                diff += 1  # 即将变成非 0
            elif count[idx_out] == 1:
                diff -= 1  # 即将变成 0
            count[idx_out] -= 1
        
        if diff == 0:
            res.append(i - len(p) + 1)
    
    return res

---

易错点

• p 比 s 长： 直接返回空列表，否则后续的 s[i - len(p)] 会取到负索引（在 Python 中会从末尾取，导致错误结果）。一定要先检查。
• 计数数组索引计算： ord(ch) - 97（或 ord(ch) - ord('a')），不是 ord(ch) 本身，也不是 ord(ch) - 96（‘a’ 的 ASCII 码是 97）。
• 窗口形成判断： if i >= len(p) 表示当索引 i 超过等于 p 长度时，窗口已满，需要移除左边界元素。注意是 >= 不是 >。
• 结果索引计算： i - len(p) + 1，不是 i 也不是 i + 1。例如 p 长度为 2，当 i=1 时窗口为 [0,1]，起始索引是 0 = 1 - 2 + 1。
• Python 列表比较： cnt_s == cnt_p 在 Python 中是逐个元素比较，虽然简洁但每次 O(26)。由于 26 很小，这个开销可以忽略，但如果字符集很大（如 256），就不建议直接用 == 了。
• p 中可能有重复字符： 计数数组需要正确统计每个字符的出现次数，p = "aab" 意味着需要 2 个 a 和 1 个 b。

---

框架提炼

定长滑动窗口模板：

核心模式：窗口大小固定，每次整体向右滑动一步，更新窗口状态，然后判断是否满足条件。

def fixed_window(s, condition_check):
    """
    定长滑动窗口通用模板
    """
    n = len(s)
    k = ...  # 窗口大小
    
    if k > n:
        return []  # 或相应默认值
    
    # 初始化窗口状态
    window_state = init_state(...)
    target_state = init_target(...)
    res = []
    
    for i in range(n):
        # 1. 加入右指针元素
        update_state(window_state, s[i], +1)
        
        # 2. 移除左指针元素（窗口满时）
        if i >= k:
            update_state(window_state, s[i - k], -1)
        
        # 3. 判断窗口状态是否满足条件
        if i >= k - 1 and matches(window_state, target_state):
            res.append(i - k + 1)  # 记录起始索引
    
    return res

定长 vs 不定长滑动窗口：

类型	窗口大小	左右指针移动	典型应用
定长	固定 k	每次右移一步，左移一步	字母异位词、大小为 k 的最大平均值
不定长	动态变化	右移扩大，左移缩小（while）	无重复子串、最小覆盖子串

---

关联题目

• 3-无重复字符的最长子串 — 不定长滑动窗口，约束条件是”窗口内无重复字符”。本题是定长窗口，约束条件是”窗口计数等于目标计数”
• 76-最小覆盖子串 — 不定长滑动窗口，本题是定长窗口。最小覆盖子串不要求窗口大小固定，而是要求覆盖目标的所有字符（可多出其他字符）
• 567-字符串的排列 — 本题的变体，判断 s2 中是否包含 s1 的排列。本质相同——找异位词，但只需要返回是否存在（true/false），不需要列出所有位置