找到字符串中所有字母异位词
Find All Anagrams in a String
在字符串 s 中找出所有长度为 p.length 的异位词子串，返回它们的起始下标。
在力扣中练习题目描述
给定两个字符串 s 和 p，找到 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" 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104s和p仅包含小写字母
解题思路
主解法
定长滑动窗口 · 字符计数
窗口每右移一格，只加一个新字符、删一个旧字符
异位词的长度一定与 p 相同，所以只需要检查所有长度为 m 的窗口。
每个窗口都重新排序是 O(n · m log m)。改成计数：用两个长度 26 的数组分别记录 p 和当前窗口的字符次数，窗口右移时只更新两个位置。
自拟主例 s = "ababac"、p = "aba"：
- 窗口
[0,2]是aba，计数一致，记录 0； - 右移成
bab，count 不一致； - 再右移成
aba，记录 2； - 最后
bac，不一致。
分步图解
先统计 p 的字符数，再看 s 的前 3 个字符窗口；计数一致，起点 0 成立。
- m
- 3
窗口大小固定，左右指针同步移动，不需要内层收缩循环。时间 O(26 · n)，26 是常数，视作 O(n)；空间 O(1)。
分步图解
窗口右移到 [2, 4]：加入 'a'、移出 'b'；计数一致，记录起点 2。
- left
- 2
- right
- 4
如果不想每次比较整个计数数组，可以额外维护一个 diff 变量，记录有多少个字符的次数不匹配，把比较降到 O(1)。
时间 O(26 · n) = O(n)空间 O(1)
易错点
- 窗口长度写成 m+1：异位词长度必须与 p 相同。
- 加入和移除的顺序无所谓，但比较必须放在两者都完成之后。
- 记录起点写成 i：窗口起点是 i-m+1，不是右端点。
- m > n 时仍访问 s[i]：需要先返回空结果。
代码与演示
演示输入
s = "ababac", p = "aba"先统计 p 的字符数，再看 s 的前 3 个字符窗口；计数一致，起点 0 成立。
- m
- 3
查看 C++ 代码
延伸阅读
- 定长窗口的题目通常都可以用“进入一个、离开一个”的增量更新，避免每步重算整段。
- 如果字符集不是小写字母，把 26 改成哈希表；比较时可以用 diff 计数保持 O(1)。