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

题意:

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

难度:

中等

示例:

解析:

第一次尝试, 想到了滑动窗口 对目标字符串排序, 排成有序字符数组 然后在窗口截取子串, 再把子串排序 匹配, 返回窗口左边界

想法很简单, 但是这里有两个问题

• 每一个子串都要排序, 复杂度是

• 这和滑动窗口的理念不符, 滑动窗口是动态确定包含的元素的, 这种方法和迭代没区别

第二次尝试, 改进滑动窗口

• 为了减少排序的复杂度, 我们使用哈希表 + 字符频率来防止排序
• 使用两个指针来维护定长窗口, 但是右指针是拓展指针, 左指针是收缩指针,