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

给定一个字符串 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" 的字母异位词。

        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> ret=new ArrayList<>();
            //排除边界条件
            if (p.length()>s.length()){
                return ret;
            }
            //子串问题，属于滑动窗口问题
            //首先定义窗口性质[left,right],窗口内为p的字母异位词，因此窗口有大小限制，与p长度相等
            //先将p转为HashMap存储便于对比
            Map<Character,Integer> pMap=new HashMap<>();
            for(int i=0;i<p.length();i++){
                char item=p.charAt(i);
                addData(item,pMap);
            }
            Map<Character,Integer> windowData=new HashMap<>();
            int left=0;
            int right=0;
            while (right<s.length()){
                char item=s.charAt(right);
                if (right-left<p.length()){
                    //当窗口还不满足数量条件时，我们直接放入数据，并右移right
                    addData(item,windowData);
                    right++;
                    continue;
                }
                System.out.println("此时的right:"+right);
                if (isAnagram(windowData,pMap)){
                    //满足异位词
                    //记录下left
                    ret.add(left);
                }
                //因为窗口数量已满足了，所以为了下一轮循环继续满足，无论是否满足异位词，均需要移除left，left进位，添加当前位,right进位
                //移除最左一位
                removeData(s.charAt(left),windowData);
                left++;
                addData(item,windowData);
                right++;
            }
            //不要漏掉最后结尾的情况，因为走完循环，此时right已经超出，所以最后一个窗口并未参与判断
            if(right-left==p.length()){
                if (isAnagram(windowData,pMap)){
                    ret.add(left);
                }
            }
            return ret;

        }
        //存入每个字符以及对应数量，因为异位词一定是所有字符都是数量相等的
        private void addData(Character key,Map<Character,Integer> map){
            if (map.containsKey(key)){
                map.put(key,map.get(key)+1);
            }else {
                map.put(key,1);
            }
        }

        private void removeData(Character key,Map<Character,Integer> map){
            if (map.get(key)>1){
                map.put(key,map.get(key)-1);
            }else {
                map.remove(key);
            }
        }

        //辅助函数，判断窗口中字符是否为p的异位词
        private boolean isAnagram(Map<Character,Integer> windowData,Map<Character,Integer> p){
            boolean ret=true;
            for (Character key:windowData.keySet()){
                //注意Integer用equals比较值
                if (!windowData.get(key).equals(p.get(key))){
                    return false;
                }
            }
            return ret;
        }