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

题目：

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

题解：滑动窗口

参考：3. 无重复字符的最长子串
滑动窗口，具体思路见代码。

代码：滑动窗口

import java.util.*;

public class code438 {

    public static List<Integer> findAnagrams(String s, String p)
    {
        // 用于返回字母异位词的起始索引
        List<Integer> res = new ArrayList<>();

        // 用 map 存储目标值中各个单词出现的次数
        HashMap<Character, Integer> map = new HashMap<>();

        for(Character c: p.toCharArray())
        {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        // 用另外一个 map(window) 存储滑动窗口中有效字符出现的次数
        HashMap<Character, Integer> window = new HashMap<>();
        int left = 0; // 左指针
        int right = 0; // 右指针
        int valid = p.length(); // 只有当 valid == 0 时，才说明 window 中包含了目标子串

        while(right < s.length())
        {
            // 如果目标子串中包含了该字符，才存入 window 中
            if(map.containsKey(s.charAt(right)))
            {
                window.put(s.charAt(right), window.getOrDefault(s.charAt(right), 0) + 1);
                // 只有当 window 中该有效字符的数量不大于 map 中该字符的数量，才能算一次有效包含
                if(window.get(s.charAt(right)) <= map.get(s.charAt(right)))
                {
                    valid--;
                }
            }
            // 如果 window 符合要求，即两个 map 存储的有效字符相同，就可以移动左指针了
            // 但是只有两个 map 存储的数据完全相同，才可以记录当前的起始索引，也就是 left 指针所在位置
            while(valid == 0)
            {
                if(right - left + 1 == p.length())
                {
                    res.add(left);
                }
                // 如果左指针指的是有效字符,需要更改 window 中的 key 对应的 value
                // 如果 window 中该有效字符的数量比目标子串少，说明无法匹配了
                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)))
                    {
                        valid++;
                    }
                }
                left++;
            }
            right++;
        }
        return res;
    }

    public static void main(String[] args) {
        String s1 = "cbaebabacd";
        String p1 = "abc";
        List<Integer> res1 = findAnagrams(s1, p1);
        System.out.println(res1.toString());

        System.out.println("***************************************");

        String s2 = "abab";
        String p2 = "ab";
        List<Integer> res2 = findAnagrams(s2, p2);
        System.out.println(res2.toString());
    }
}

参考：

1. 我写了一首诗，把滑动窗口算法变成了默写题
2. 2020.03.21（438，median）
3. 场景类比：新员工入职 + 老员工离职
4. Java优化labuladong大佬滑动窗口通用方法