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

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

• 1 <= s.length, p.length <= 3 * 104

• s 和 p 仅包含小写字母

1. 数据结构

• 使用两个哈希表：need 存储目标字符串p中字符的频次，window存储当前窗口中字符的频次

• 使用valid变量记录当前窗口中满足条件的字符个数

• 使用vector存储结果索引

2. 算法流程

初始化

• 统计字符串p中每个字符的频次，存入need哈希表

• 初始化左右指针i, j为0

滑动窗口过程

• 扩大窗口：- 右指针i向右移动，将新字符加入窗口- 如果该字符在need中存在，更新window中的频次- 如果该字符在window中的频次等于need中的频次，valid加1

• 缩小窗口：- 当窗口大小大于p的长度时，需要缩小窗口- 如果valid等于need的大小，说明找到一个异位词，记录左指针位置- 移出最左边的字符，更新相关计数- 左指针j向右移动

3. 时间复杂度分析

• 时间复杂度：O(n)，其中n为字符串s的长度

• 空间复杂度：O(k)，其中k为字符集大小，本题中字符集为小写字母，所以k=26

4. 关键点

• 使用valid变量来优化判断条件，避免每次都要比较两个哈希表

• 通过比较字符频次来判断是否为异位词，而不是对子串排序

• 滑动窗口的大小固定为字符串p的长度

5. 注意事项

• 需要特别注意窗口大小的控制

• 更新valid值的时机：当字符频次相等时增加，不相等时减少

• 处理边界情况，确保不会发生越界