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

题目链接（中等）

题目描述

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

数据范围：

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

示例

示例 1：

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

示例 2：

输入： s = "abab", p = "ab"
输出： [0,1,2]
解释： - 起始索引等于 0 的子串是 "ab"，它是 "ab" 的异位词。 - 起始索引等于 1 的子串是 "ba"，它是 "ab" 的异位词。 - 起始索引等于 2 的子串是 "ab"，它是 "ab" 的异位词。

核心思路

异位词的性质：两个字符串互为字母异位词，当且仅当它们字母的种类和数量完全相同。

滑动窗口：

• 因为 p 的异位词长度一定等于 p 的长度，所以可以在 s 上维护一个长度为 len(p) 的滑动窗口；
• 每次滑动后，比较窗口内字母计数与 p 的字母计数；
• 若相同，说明当前窗口是 p 的一个异位词。

两种实现：

1. 数组计数：用两个长度为 26 的数组分别统计窗口和 p 的字母数量，每次比较数组是否相等；
2. 差值 + differ 变量：只用一个数组记录差值，用 differ 记录「计数不同的字母个数」，把每次比较从 $O(\Sigma)$ 降到 $O(1)$。

---

方法一：滑动窗口 + 数组计数

思路及解法

预处理：

• 若 len(s) < len(p)，直接返回 []；
• 用两个长度 26 的数组分别统计 p 和初始窗口（s[0..p_len-1]）的字母数量。

滑动过程：

1. 判断初始窗口是否等于 p 的计数，是则加入 0；
2. 窗口每次向右滑动一格：
   • 移除左边的字符 s[i]；
   • 加入右边的字符 s[i + p_len]；
   • 再次比较两个计数数组，相等则把 i + 1 加入答案。

比较操作：直接比较两个 list 是否相等，Python 会自动逐元素比较，复杂度 $O(\Sigma) = O(26)$。

代码

class Solution:
    def findAnagrams(self, s: str, p: str) -> list[int]:
        s_len, p_len = len(s), len(p)

        if s_len < p_len:
            return []

        ans = []
        s_count = [0] * 26
        p_count = [0] * 26

        # 初始化窗口和 p 的字母计数
        for i in range(p_len):
            s_count[ord(s[i]) - 97] += 1
            p_count[ord(p[i]) - 97] += 1

        if s_count == p_count:
            ans.append(0)

        # 滑动窗口
        for i in range(s_len - p_len):
            s_count[ord(s[i]) - 97] -= 1            # 移除左端
            s_count[ord(s[i + p_len]) - 97] += 1    # 加入右端

            if s_count == p_count:
                ans.append(i + 1)

        return ans

复杂度分析

• 时间复杂度：$O(m + (n-m) \cdot \Sigma)$，其中 $n$ 为 s 的长度，$m$ 为 p 的长度，$\Sigma = 26$。初始化 $O(m)$，滑动共 $n - m$ 次，每次比较 $O(\Sigma)$。
• 空间复杂度：$O(\Sigma)$，两个长度为 26 的数组。

---

方法二：优化滑动窗口（差值 + differ）✅ 推荐

思路及解法

方法一每次滑动后都要比较整个计数数组，$O(\Sigma)$。其实滑动时只改变两个字母的计数，其余都没变，可以利用这个特性把比较降到 $O(1)$。

核心改进：

• 用一个数组 count 存储「窗口和 p 的字母数量之差」：count[i] = 窗口内字母 i 的数量 - p 内字母 i 的数量；
• 用变量 differ 记录「count 中不为 0 的位置个数」，即「有多少个字母的计数不同」；
• 当 differ == 0 时，说明窗口就是 p 的异位词。

滑动窗口时的更新：

• 移除左端字符 s[i]：
  • count[s[i]] -= 1 后，若 count[s[i]] 变为 0，说明该字母从「不同」变成「相同」，differ -= 1；
  • 若 count[s[i]] 变为 -1，说明该字母从「相同」变成「不同」，differ += 1；
• 加入右端字符 s[i + p_len]：
  • count[s[i + p_len]] += 1 后，若变为 0，differ -= 1；
  • 若变为 1，differ += 1。

关键：每次只检查两个字符的计数变化，就能正确维护 differ。

代码

class Solution:
    def findAnagrams(self, s: str, p: str) -> list[int]:
        s_len, p_len = len(s), len(p)

        if s_len < p_len:
            return []

        ans = []
        count = [0] * 26

        # 计算差值：窗口（前 p_len 个字符） - p
        for i in range(p_len):
            count[ord(s[i]) - 97] += 1
            count[ord(p[i]) - 97] -= 1

        # 统计有多少个字母的计数不同
        differ = sum(1 for c in count if c != 0)

        if differ == 0:
            ans.append(0)

        # 滑动窗口
        for i in range(s_len - p_len):
            # 移除左端字符 s[i]
            idx = ord(s[i]) - 97
            if count[idx] == 1:
                differ -= 1
            elif count[idx] == 0:
                differ += 1
            count[idx] -= 1

            # 加入右端字符 s[i + p_len]
            idx = ord(s[i + p_len]) - 97
            if count[idx] == -1:
                differ -= 1
            elif count[idx] == 0:
                differ += 1
            count[idx] += 1

            if differ == 0:
                ans.append(i + 1)

        return ans

复杂度分析

• 时间复杂度：$O(n + m + \Sigma)$，初始化差值 $O(m)$，初始化 differ $O(\Sigma)$，滑动共 $n - m$ 次，每次更新 $O(1)$。
• 空间复杂度：$O(\Sigma)$，一个长度为 26 的差值数组。

---

两种方法对比

方法	时间	空间	特点
数组计数	$O(m + (n-m) \cdot \Sigma)$	$O(\Sigma)$	思路直观，代码简单
差值 + differ	$O(n + m + \Sigma)$	$O(\Sigma)$	每次判断 $O(1)$，效率最优

推荐：

• 面试开场：先写方法一，讲清滑动窗口的框架；
• 追问优化：再写方法二，展示「只关心变化量」的优化思路。

---

关键细节

1. 为什么可以用固定长度的滑动窗口

因为异位词的长度一定等于 p 的长度，所以窗口长度固定为 p_len，不需要像「最小覆盖子串」那样用双指针动态扩展/收缩。

2. count 的差值含义

count[i] = 窗口内字母 i 的数量 - p 内字母 i 的数量。

• count[i] == 0：字母 i 的计数相同；
• count[i] > 0：窗口内字母 i 比 p 多；
• count[i] < 0：窗口内字母 i 比 p 少。

当所有 count[i] == 0 时，窗口就是 p 的异位词。

3. differ 的更新逻辑

移除左端字符（count[idx] -= 1 之前）：

变化前 count[idx]	变化后	differ 变化	原因
1	0	-1	从「不同」变成「相同」
0	-1	+1	从「相同」变成「不同」
其他	—	不变	仍是不同

加入右端字符（count[idx] += 1 之前）：

变化前 count[idx]	变化后	differ 变化	原因
-1	0	-1	从「不同」变成「相同」
0	1	+1	从「相同」变成「不同」
其他	—	不变	仍是不同

记忆口诀：变化后变成 0 → differ - 1；变化前是 0 → differ + 1。

4. 与 LC 49（字母异位词分组）的区别

	LC 49	LC 438
目标	把所有异位词分组	在 s 中找 p 的异位词子串
方法	哈希表 + 排序 / 计数	滑动窗口 + 计数
关键	找到「同一个键」	维护固定长度的窗口

5. differ 初始化可以用 sum

differ = sum(1 for c in count if c != 0)

等价于：

differ = [c != 0 for c in count].count(True)

两者效果相同，前者更 Pythonic。

---

总结

• 核心思路：异位词长度相同，用长度为 p_len 的滑动窗口比较字母计数；
• 方法一：
  • 用两个计数数组分别记录窗口和 p 的字母数量；
  • 每次滑动后比较数组是否相等；
  • 时间 $O(m + (n-m) \cdot \Sigma)$；
• 方法二（推荐）：
  • 用一个差值数组 count = 窗口 - p；
  • 用 differ 维护「计数不同的字母个数」；
  • 每次滑动只更新两个字母，O(1) 判断；
  • 时间 $O(n + m + \Sigma)$；
• 通用套路：固定长度滑动窗口 + 哈希 / 计数，用于处理「子串匹配」类问题。

相关题目

• LC 49. 字母异位词分组（哈希 + 排序）
• LC 567. 字符串的排列（判断 s2 是否包含 s1 的异位词）
• LC 76. 最小覆盖子串（不定长滑动窗口）
• LC 3. 无重复字符的最长子串（不定长滑动窗口）
• LC 992. K 个不同整数的子数组（滑动窗口计数）