一、思路

这题虽然也是滑动窗口，但是是属于比较“死板”的滑动窗口，因为它的窗口是固定的，所以有相对简单的解法。我将两种解法都写出来了（简单解法和滑动窗口一般解法）。

二、题目

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

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

说明：

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

示例 1:

输入:
s: "cbaebabacd" p: "abc"

输出:
[0, 6]

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

 示例 2:

输入:
s: "abab" p: "ab"

输出:
[0, 1, 2]

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

\n

三、代码

class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            HashMap<Character, Integer> needs = new HashMap<>();
            HashMap<Character, Integer> window = new HashMap<>();
            ArrayList<Integer> ans = new ArrayList<>();
            int valid = 0;
            for (char c :
                    p.toCharArray()) {
                needs.put(c, needs.getOrDefault(c, 0) + 1);
            }
            for (int i = 0; i < p.length() && i < s.length(); i++) {
                window.put(s.charAt(i), window.getOrDefault(s.charAt(i), 0) + 1);
                if (window.get(s.charAt(i)).equals(needs.get(s.charAt(i)))) {
                    valid++;
                }
            }
            if (valid == needs.size() && valid != 0) {
                ans.add(0);
            }
            for (int i = 0; i < s.length() - p.length(); i++) {
                if (needs.containsKey(s.charAt(i))) {
                    if (needs.get(s.charAt(i)).equals(window.get(s.charAt(i)))) {
                        valid--;
                    }
                    window.put(s.charAt(i), window.get(s.charAt(i)) - 1);
                }
                char c = s.charAt(i + p.length());
                if (needs.containsKey(c)) {
                    window.put(c, window.getOrDefault(c, 0) + 1);
                    if (needs.get(c).equals(window.get(c))) {
                        valid++;
                    }
                }
                if (valid == needs.size()) {
                    ans.add(i + 1);
                }
            }
            return ans;
        }

        public List<Integer> findAnagrams1(String s, String p) {
            HashMap<Character, Integer> needs = new HashMap<>();
            HashMap<Character, Integer> window = new HashMap<>();
            ArrayList<Integer> ans = new ArrayList<>();
            for (char c :
                    p.toCharArray()) {
                needs.put(c, needs.getOrDefault(c, 0) + 1);
            }
            int left = 0;
            int right = 0;
            int valid = 0;
            while (right < s.length()) {
                char c = s.charAt(right++);
                if (needs.containsKey(c)) {
                    window.put(c, window.getOrDefault(c, 0) + 1);
                    if (needs.get(c).equals(window.get(c))) {
                        valid++;
                    }
                }
                while (right - left >= p.length()) {
                    if (valid == needs.size()) {
                        ans.add(left);
                    }
                    char c1 = s.charAt(left++);
                    if (needs.containsKey(c1)) {
                        if (window.get(c1).equals(needs.get(c1))) {
                            valid--;
                        }
                        window.put(c1, window.get(c1) - 1);
                    }
                }
            }
            return ans;
        }
    }