力扣算法笔试题复习:【滑动窗口】找到字符串中所有字母异位词

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

原题地址：

https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/

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

所谓字母异位词，就是两个字符串使用的字符种类和每种字符出现次数完全相同，只是排列顺序可以不同。比如 "abc"、"bac"、"cba" 都互为字母异位词；但 "abb" 和 "abc" 就不是，因为字符出现次数不同。

举个例子：

输入：

s = "cbaebabacd"p = "abc"

输出：

[0, 6]

原因是：

• 下标 0 开始的子串 "cba" 是 "abc" 的异位词；
• 下标 6 开始的子串 "bac" 也是 "abc" 的异位词。

再看一个：

s = "abab"p = "ab"

输出：

[0, 1, 2]

因为 "ab"、"ba"、"ab" 都是 "ab" 的异位词。

这道题的核心其实很明确：在 s 中不断截取长度为 len(p) 的子串，判断这个子串是否和 p 具有相同的字符组成。如果相同，就记录当前起始下标。

第一种：固定长度窗口 + 排序比较

最直接的想法是：因为要找的是 p 的异位词，所以目标子串的长度一定和 p 相同。于是可以在 s 上维护一个长度固定为 len(p) 的窗口，每次截取一个子串，将这个子串排序后与排序后的 p 比较。

如果两个排序结果相同，说明它们字符组成一致，也就是字母异位词。

classSolution:deffindAnagrams(self, s: str, p: str) -> list[int]:        result = []        window_size = len(p)        sorted_p = sorted(p)        start = 0while start + window_size <= len(s):            window = s[start:start + window_size]if sorted(window) == sorted_p:                result.append(start)            start += 1return result

这段代码的逻辑非常直接：

• window_size = len(p)：固定窗口长度；
• sorted_p = sorted(p)：提前对 p 排序，避免每次重复排序；
• 每次从 s 中截取长度为 window_size 的子串；
• 对当前子串排序后与 sorted_p 比较；
• 如果相等，说明当前窗口是一个合法异位词，记录起始下标。

以 s = "cbaebabacd"、p = "abc" 为例：

• s[0:3] = "cba"，排序后是 ['a', 'b', 'c']，命中，记录 0；
• s[1:4] = "bae"，排序后不是 ['a', 'b', 'c']，跳过；
• ...
• s[6:9] = "bac"，排序后是 ['a', 'b', 'c']，命中，记录 6。

这种写法非常容易理解，本质上就是枚举每一个长度为 len(p) 的候选子串，然后判断它是不是异位词。

不过它的问题也比较明显：每移动一次窗口，都需要对子串重新排序。如果 p 的长度是 m，排序一次的复杂度是 O(m log m)；而窗口最多会移动 n - m + 1 次，所以整体时间复杂度是：

O((n - m + 1) * m log m)

近似记为 O(n * m log m)。

空间复杂度主要来自排序产生的临时数组，为 O(m)。

这种方法适合作为入门理解，但如果数据规模较大，重复排序会带来不必要的开销。

第二种：滑动窗口 + 字符频次统计

判断两个字符串是否为异位词，本质上不需要排序。只要它们的字符频次完全一致，就一定是异位词。

因此可以用哈希表或数组统计字符出现次数。由于本题通常只涉及英文小写字母，所以可以用长度为 26 的数组表示字符频次：

• target_count 记录 p 中每个字符出现的次数；
• window_count 记录当前窗口中每个字符出现的次数；
• 当两个数组相等时，说明当前窗口是 p 的异位词。

classSolution:deffindAnagrams(self, s: str, p: str) -> list[int]:        result = []        s_len, p_len = len(s), len(p)if s_len < p_len:return result        target_count = [0] * 26        window_count = [0] * 26for char in p:            target_count[ord(char) - ord('a')] += 1for right in range(s_len):# 右侧字符进入窗口            right_char_index = ord(s[right]) - ord('a')            window_count[right_char_index] += 1# 当窗口长度超过 p_len 时，左侧字符移出窗口if right >= p_len:                left_char_index = ord(s[right - p_len]) - ord('a')                window_count[left_char_index] -= 1# 窗口长度达到 p_len 后，开始判断是否匹配if right >= p_len - 1:if window_count == target_count:                    start = right - p_len + 1                    result.append(start)return result

这版写法的核心是维护一个固定长度的滑动窗口。

右指针 right 不断向右移动，每次把 s[right] 加入窗口。当窗口长度超过 p_len 时，就把最左侧那个字符移出窗口。这样可以保证窗口始终最多只有 p_len 个字符。

当 right >= p_len - 1 时，说明窗口长度已经达到 p_len，此时就可以判断当前窗口的字符频次是否等于 p 的字符频次。如果相等，当前窗口就是一个异位词，起始位置为：

right - p_len + 1

比如 s = "cbaebabacd"，p = "abc"：

• 当窗口为 "cba" 时，字符频次和 "abc" 一致，记录下标 0；
• 窗口继续右移；
• 当窗口变成 "bac" 时，字符频次再次一致，记录下标 6。

这种方法避免了每次对子串排序，窗口每移动一步只做两件事：

1. 加入一个新字符；
2. 移除一个旧字符。

由于字符集大小固定为 26，比较两个长度为 26 的数组可以视为常数时间。因此整体时间复杂度是 O(n)，空间复杂度是 O(1)。

总结

这道题本质上是在字符串 s 中寻找所有长度固定为 len(p) 的窗口，并判断窗口内字符频次是否与 p 一致。

排序比较的写法最直观，但每个窗口都要重新排序，时间开销较大；滑动窗口配合字符频次数组，可以在窗口右移时增量维护状态，把整体复杂度优化到 O(n)。一句话总结：异位词判断看字符频次，固定长度子串问题优先考虑滑动窗口。