438. 找到字符串中所有字母异位词(困难)

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。

示例 1:

1
2
3
4
5
6
7
8
9
输入:
s: "cbaebabacd" p: "abc"

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

示例 2:

1
2
3
4
5
6
7
8
9
10
输入:
s: "abab" p: "ab"

输出:
[0, 1, 2]

解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string

思路：

滑动窗口，基于模板

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
    public List<Integer> findAnagrams(String s, String p) {

        //滑动窗口
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();
        //统计t中各元素个数
        //for(int i =0 ;i<t.length();i++){
        //    Character key = t.charAt(i);
        //    need.put(key,need.getOrDefault(key,0)+1);
        //}
        for(char c : p.toCharArray()){
            need.put(c,need.getOrDefault(c,0)+1);
        }
        //开始定义窗口双指针
        int left =0,right=0;
        int count = 0;//这个用来记录
        List<Integer> res = new ArrayList<>();
        while(right<s.length()){
            //获取移入窗口的值
            char c = s.charAt(right);
            right++;
            //窗口更新
            //如果移入的值在所需的字符串中
            if(need.containsKey(c)){
                //窗口+1
                window.put(c,window.getOrDefault(c,0)+1);
                //如果需要的个数正好满足
                if(window.get(c).equals(need.get(c))){
                    count++;
                }
            }
            //确定左边是否要收缩
            while (right-left>=p.length()){

                //判断长度是否可以更新
                if(count==need.size()){
                    //需要记录一下开始的索引
                    res.add(left);
                }
                //移动左边，窗口缩小
                char c1 = s.charAt(left);
                left++;
                //开始更新窗口内容
                //如果当前要移动的字符是包含在need中，我们需要进行讨论，如果该字符的次数刚好与我们需要的次数相等，则valid--，并同时更新window中这个值出现的次数
                if(need.containsKey(c1)){
                    //左边有重复的
                    if(window.get(c1).equals(need.get(c1))){
                        count--;
                    }
                    window.put(c1,window.getOrDefault(c1,0)-1);
                }
            }
        }
        //返回
        return res;
    }
}