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

简书来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string

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

双指针+Map解法（较为繁琐）：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        if(s.length() < p.length())
            return ans;
        Map<Character,Integer> map = new HashMap<>();
        for(char c : p.toCharArray()){
            map.merge(c,1,Integer::sum);
        }
        //多余的字母
        Map<Character,Integer> surplus = new HashMap<>();
        //缺少的字母
        Map<Character, Integer> lack = new HashMap<>(map);
        int left = 0;
        int right = p.length() - 1;
        int tmp = 0;
        while(tmp <= right){
            char c = s.charAt(tmp);
            add(map,surplus,lack,c);
            tmp++;
        }
        //如果既不多也不缺，就说明刚刚好
        if (surplus.isEmpty() && lack.isEmpty()){
            ans.add(left);
        }
        while(right < s.length()-1){
            //移除一个元素
            remove(map,surplus,lack,s.charAt(left));
            left++;
            right++;
            //新加一个元素
            add(map,surplus,lack,s.charAt(right));
            if (surplus.isEmpty() && lack.isEmpty()){
                ans.add(left);
            }
        }
        return ans;
    }

    private void remove(Map<Character,Integer> map ,Map<Character,Integer> surplus,Map<Character,Integer> lack,Character c){
        if (surplus.get(c) != null){
            //多余的元素
            Integer i = surplus.get(c);
            if(i == 1){
                surplus.remove(c);
            }else{
                surplus.put(c,i-1);
            }
        }else if(map.get(c) != null){
            //移除之后缺少了
            lack.merge(c,1,Integer::sum);
        }
    }

    private void add(Map<Character,Integer> map ,Map<Character,Integer> surplus,Map<Character,Integer> lack,Character c){
        if (map.get(c) == null || lack.get(c) == null){
            //说明多余
            surplus.merge(c,1,Integer::sum);
        }else if (lack.get(c) != null){
            //补充缺少的
            Integer i = lack.get(c);
            if (i == 1){
                lack.remove(c);
            }else{
                lack.put(c,i-1);
            }
        }
    }
}