438.找到字符串中所有字母异位词

题目描述

题解

滑动窗口

可以使用全排列的方法把所有的排列组合放到哈希表中, 然后逐个遍历字符串, 截取适当的长度去匹配, 但是时间复杂度不好, 因此采用滑动窗口的方式.

public List<Integer> findAnagrams(String s, String p) {

    List<Integer> res = new ArrayList<>();
    HashMap<Character, Integer> map = new HashMap<>();
    HashMap<Character, Integer> window = new HashMap<>();

    char[] chars = p.toCharArray();
    for (char c : chars) {
        map.put(c, map.getOrDefault(c, 0) + 1);
    }

    int left = 0;
    int right = 0;
    int value = p.length();

    while (right < s.length()) {
        if (map.containsKey(s.charAt(right))) {
            window.put(s.charAt(right), window.getOrDefault(s.charAt(right), 0) + 1);
            if (window.get(s.charAt(right)) <= map.get(s.charAt(right))) {
                value--;
            }
        }

        while (value == 0) {
            if (right - left + 1 == p.length()) {
                res.add(left);
            }
            if (map.containsKey(s.charAt(left))) {
                window.put(s.charAt(left), window.get(s.charAt(left)) - 1);
                if (window.get(s.charAt(left)) < map.get(s.charAt(left))) {
                    value++;
                }
            }
            left++;
        }
        right++;
    }

    return res;
}