438. 找到字符串中所有字母异位词 (opens new window)

解题思路：滑动窗口+哈希

用哈希表保存模式串p中每个字符的使用次数。如果当前指针i对应的字符满足条件则进入匹配：

• 尾指针先向右移动进行模式匹配，直至当前尾指针指向的字符不满足条件。期间如果当前匹配长度和模型串长度相同，那么得到一个异位词子串，并记录当前头指针索引结果。
• 当尾指针走不动路之后(①当前尾指针指向的字符不在模式串中②当前尾指针指向字符的使用频次为0)，头指针开始向右边移动缩小滑动窗口。缩减当前匹配次数，恢复释放哈希表中的头指针字符使用频次。
• 头尾指针第二次相撞时，需要从头另起一个匹配串。

class Solution {
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        HashMap<Character, Integer> hashmap = new HashMap<>();
        for (int i = 0; i < p.length(); i++) {
            hashmap.put(p.charAt(i), hashmap.getOrDefault(p.charAt(i), 0) + 1);
        }
        int length = 0;
        for (int i = 0; i < s.length(); i++) {
            if (hashmap.containsKey(s.charAt(i))) {
                int head = i;
                int tail = head;
                while (head <= tail) {
                    if (hashmap.containsKey(s.charAt(tail)) && hashmap.get(s.charAt(tail)) > 0) {
                        hashmap.put(s.charAt(tail), hashmap.get(s.charAt(tail)) - 1);
                        tail++;
                        length++;
                        if (length == p.length()) {
                            res.add(head);
                        }
                        if (tail == s.length()) {
                            return res;
                        }
                    } else {
                        hashmap.put(s.charAt(head), hashmap.get(s.charAt(head)) + 1);
                        head++;
                        length--;
                        if (head == tail) {
                            break;
                        }
                    }
                }
                i = head - 1;
            }
        }
        return res;
    }
}