essay
hot100-找到字符串中所有字母异位词
#算法
hot100——找到字符串中所有字母异位词
给定两个字符串 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 仅包含小写字母
解
// findAnagrams 找出字符串 s 中所有 p 的字母异位词的起始索引
func findAnagrams(s string, p string) []int {
// arr 用于记录“还需要多少个字符”才能匹配 p
// 初始时：arr[c] = p 中字符 c 的出现次数
// 随着遍历 s，我们“消耗”这些次数（做减法）
arr := [26]int{}
// 滑动窗口左边界（包含）
left := 0
// 存储结果（所有异位词的起始位置）
result := []int{}
// 初始化 arr：统计 p 中每个字符的频次
for _, c := range p {
arr[c-'a']++ // 'a'→0, 'b'→1, ..., 'z'→25，得到的结果就是arr[0]=1/0('a'出现一次或0次),arr[1]=1/0('b'出现一次或0次)
}
// right 是滑动窗口的右边界（包含），遍历 s
for right := 0; right < len(s); right++ {
// 将 s[right] 加入窗口：消耗一个该字符的“配额”
arr[s[right]-'a']--
// 如果某个字符被“过度消耗”（< 0），说明窗口内该字符太多
// → 需要移动左边界，直到不再超额
for arr[s[right]-'a'] < 0 {
// 把 left 处的字符“归还”（因为它要被移出窗口）
arr[s[left]-'a']++
left++
}
// 当前窗口 [left, right] 是无超额的（即所有字符数量 ≤ p 中的数量）
// 如果窗口长度正好等于 len(p)，说明字符种类和数量完全匹配！
if right-left+1 == len(p) {
result = append(result, left)
}
}
return result
}