438. 找所有字母异位词

题目

https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

思路

代码

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        unordered_map<char, int> need, window;
        int vaild = 0;
        for (char c : p) need[c]++;
        int left = 0, right = 0;
        while(right<s.size()){
            char c = s[right];
            right++;
            if(need.count(c)){
                window[c]++;
                if(window[c]==need[c]){
                    vaild++;
                }
            }
            while(right-left>=p.size()){
                if(vaild==need.size()){
                    res.push_back(left);
                }
                char t = s[left];
                left++;
                if(need.count(t)){
                    if(window[t]==need[t]){
                        vaild--;
                    }
                    window[t]--;
                }
                
            }
        }
        return res;
    }
};