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

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 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" 的异位词。

提示:

• 1 <= s.length, p.length <= 3 * 104
• s 和 p 仅包含小写字母

使用map记录p中的字母和词频

维护[left, right]中字符串中字母的map都 > =0

如果遇到s[right]使得map中元素<0，说明不需要该字母，此时需要移动 left 使得 s[right]在map中变为0 ，left 移动过程中的字母词频都要加回来，因为r在移动过程已经把这部分的词频减去

有两种情况使得map中元素 < 0

• s[right]为p的元素，如s = cabc , p = abc ； 此时[left, right] = cab满足情况加入到ans，然后right移动到3使得map[c] < 0，需要移动left，当left == 1，map[c] = 0，[l, r] = abc满足情况，加入ans。
• s[right]不为p的元素，如s = aeabc, p = abc；此时right移动到e，使得map[e] < 0, 需要移动left，当left == 2，map[e] == 0，最终left == 2，right ==2，重新开始统计

如果r - l + 1 为p的长度，则[l, r]满足条件，因为如果遇到s[r]使得map中元素<0，需要移动l，[l, r]的长度必定小于p的长度，[l, r]的长度为p的长度，此时map中元素都为0

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int s_len = s.length();
        int p_len = p.length();
        int[] hashmap = new int[26];
        for(int i = 0; i < p_len; i++){
            hashmap[p.charAt(i) - 'a'] ++;
        }
        int left = 0;
        int right = 0;
        while(right < s_len){
            char c = s.charAt(right);
            hashmap[c - 'a'] --;//遇到的单词词频减1
            while(hashmap[c - 'a'] < 0){ //词频小于0，说明不需要该单词，移动l并把词频加回来，直到r==0
                char lchar = s.charAt(left);
                hashmap[lchar - 'a'] ++;
                left ++;
            }
            if(right - left + 1 == p_len){
                ans.add(left);
            }
            right ++; 
        }
        return ans;
    }
}