leetcode438.寻找字符串中所有字符异位词

滑动窗口

leetcode438.寻找字符串中所有字符异位词

基本思路

1.窗口不断加入字符，扩大范围，直到找到符合条件的子串

2.窗口缩小，直到不符合条件，记得更新结果

3.重复1，2步，直到r达到字符串s的结尾

解法代码

func findAnagrams(s string, p string) []int {
	window := make(map[byte]int, 0)
	need := make(map[byte]int, 0)
	res := make([]int, 0)
	l, r, valid := 0, 0, 0
	for i, _ := range p {
		need[p[i]]++
	}

	for r < len(s) {
		c := s[r]
		r++
		if _, ok := need[c]; ok {
			window[c]++
			if window[c] == need[c] {
				valid++
			}
		}

		for valid == len(need) {
			if r-l == len(p) {
				res = append(res, l)
			}

			d := s[l]
			l++

			if _, ok := need[d]; ok {
				if window[d] == need[d] {
					valid--
				}
				window[d]--
			}
		}
	}
	return res
}