2021-12-18：找到字符串中所有字母异位词。 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成

2021-12-18：找到字符串中所有字母异位词。
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
力扣438。

答案2021-12-18：

滑动窗口。欠账表。
时间复杂度：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
}

执行结果如下：

左神java代码