找到字符串中所有字母异位词。
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
滑动窗口。欠账表。
时间复杂度：O(N)。
空间复杂度：O(1)。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
s := "abab"
p := "ab"
ret := findAnagrams(s, p)
fmt.Println(ret)
}
func findAnagrams(s, p string) []int {
ans := make([]int, 0)
if len(s) < len(p) {
return ans
}
str := []byte(s)
N := len(str)
pst := []byte(p)
M := len(pst)
map0 := make(map[byte]int)
for _, cha := range pst {
map0[cha]++
}
all := M
for end := 0; end < M-1; end++ {
if _, ok := map0[str[end]]; ok {
count := map0[str[end]]
if count > 0 {
all--
}
map0[str[end]] = count - 1
}
}
for end, start := M-1, 0; end < N; end, start = end+1, start+1 {
if _, ok := map0[str[end]]; ok {
count := map0[str[end]]
if count > 0 {
all--
}
map0[str[end]] = count - 1
}
if all == 0 {
ans = append(ans, start)
}
if _, ok := map0[str[start]]; ok {
count := map0[str[start]]
if count >= 0 {
all++
}
map0[str[start]] = count + 1
}
}
return ans
}执行结果如下：
