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

public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();

        if (s.length() < p.length()) {
            return ans;
        }

        int[] arrP = new int[26]; // 统计p的字符出现次数
        int[] arrS = new int[26]; // 统计s滑动窗口内的字符出现次数

        for (int i = 0; i < p.length(); i++) {
            arrP[p.charAt(i) - 'a']++; // p的第i个字符对应数组下标，计数+1
            arrS[s.charAt(i) - 'a']++; // 先统计s前p.length()个字符的计数
        }

        // 用于比较两个数组的内容是否完全相等
        if (Arrays.equals(arrP, arrS)) {
            ans.add(0);
        }

        // 初始窗口是[0, p.length()-1]，右边界从p.length()开始
        int left = 0;
        int right = p.length();

        while (right < s.length()) {
            // 右边界字符加入窗口：计数+1
            arrS[s.charAt(right) - 'a']++;
            // 左边界字符移出窗口：计数-1
            arrS[s.charAt(left) - 'a']--;

            // 窗口右移：左、右边界各+1
            left++;
            right++; 
                       
            // 此时窗口起始下标是left，判断是否匹配
            if (Arrays.equals(arrP, arrS)) {
                ans.add(left);
            }


        }

        return ans;
    }