【每日一题】Day 6

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

题目：

给定两个字符串 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 * 104
s 和 p 仅包含小写字母

---

思路：

统计目标字符串 p 的字符频率。
在 s 上用一个固定长度为 len(p) 的滑动窗口，维护窗口内的字符频率。
每次窗口右移：加入一个新字符，移除一个旧字符。
比较窗口频率和 p 的频率，如果相同，就记录当前窗口起始位置。
滑动到结尾，返回所有起始索引。

---

代码实现（Go）：

详细注解：

//package main
//
//import "fmt"func findAnagrams(s string, p string) []int {res := []int{} // 用于存放结果的切片if len(s) < len(p) {return res // 如果s比p短，不可能有异位词，直接返回空数组}// 定义两个长度为26的数组，用于存储字符频率// 下标 0~25 对应 'a'~'z'// pCount：模板的字母频率// winCount：当前窗口里的字母频率var pCount, winCount [26]int// 初始化当前窗口并统计 p 的字符频率for i := 0; i < len(p); i++ {pCount[p[i]-'a']++   // 统计 p 中每个字母出现次数winCount[s[i]-'a']++ // 当前窗口的字母计数，初始化为s的前len(p)个字符的频率}// 检查第一个窗口是否和 p 的字母计数相等// 如果相等，则第一个窗口就是一个异位词if winCount == pCount {res = append(res, 0) // 初始窗口起始索引为0}// 从第 len(p) 个字符开始，向右滑动窗口遍历 s 的剩余部分// i 是当前窗口右边新加进来的字符的下标for i := len(p); i < len(s); i++ {winCount[s[i]-'a']++        // 加入新字符到窗口并计数winCount[s[i-len(p)]-'a']-- // 移除窗口最左边的旧字符// 判断当前窗口计数是否和 p 相等// 如果相等，说明找到了一个异位词，记录起始索引if winCount == pCount {res = append(res, i-len(p)+1)}}return res
}//func main() {
//	s, p := "cbaebabacd", "abc"
//	fmt.Println(findAnagrams(s, p)) // 输出: [0,6]
//}

无注释：

//package main
//
//import "fmt"func findAnagrams(s string, p string) []int {res := []int{}if len(s) < len(p) {return res}var pCount, winCount [26]intfor i := 0; i < len(p); i++ {winCount[s[i]-'a']++pCount[p[i]-'a']++}if winCount == pCount {res = append(res, 0)}for i := len(p); i < len(s); i++ {winCount[s[i]-'a']++winCount[s[i-len(p)]-'a']--if winCount == pCount {res = append(res, i-len(p)+1)}}return res
}//func main() {
//	s, p := "cbaebabacd", "abc"
//	fmt.Println(findAnagrams(s, p)) // 输出: [0,6]
//}

---