找到字符串中所有字母异位词(异位词统计)

短命女 2022-10-29 09:26 148阅读 0赞

\#\#\# 解题思路

首先利用哈希表保存s1中字符出现的次数

利用双指针在s2中维护一段长度为s1的滑动窗口,然后统计这段窗口中的字符出现次数是否与s1一致

把符合条件的字符串首字母加入哈希表

\#\#\# 代码

class Solution {
    public:
        unordered_map<char,int> hm1,hm2;
        vector<int> findAnagrams(string s, string p) {
            vector<int> res;
            for(int i = 0; i < p.size();++i) hm1[p[i]]++;  
            int p1 = 0,p2 = 0;
            for(;p2<p.size();++p2) hm2[s[p2]]++;
            while(p2 < s.size()){
                bool flag = true;
                for(int k = 'a'; k <= 'z'; ++k){
                    if(hm1[k] != hm2[k]){
                       flag = false;
                       break;
                    }
                }
                if(flag) res.push_back(p1);
                hm2[s[p2++]]++;
                hm2[s[p1++]]--;
            }
            bool flag = true;
            for(int k = 'a'; k <= 'z'; ++k){
                if(hm1[k] != hm2[k]){
                    flag = false;
                    break;
                }
            }
            if(flag) res.push_back(p1);
            return res;
        }
    };