模块二——滑动窗口：438.找到字符串中所有字母异位词

题目描述

题目链接：438.找到字符串中所有字母异位词

算法原理

滑动窗口+哈希表

• 因为字符串p的异位词的?度?定与字符串p 的?度相同，所以我们可以在字符串s 中构造?个?度为与字符串p的?度相同的滑动窗?，并在滑动中维护窗?中每种字?的数量；
• 当窗?中每种字?的数量与字符串p 中每种字?的数量相同时，则说明当前窗?为字符串p的异位词；
• 因此可以?两个??为26 的数组来模拟哈希表，?个来保存s 中的?串每个字符出现的个数，另?个来保存p中每?个字符出现的个数。这样就能判断两个串是否是异位词。

代码实现

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int hash1[26] = { 0 };//统计字符串p中每个字符出现的个数
        for(auto ch : p)hash1[ch - 'a']++;
        int hash2[26] = { 0 };//统计窗口里面每一个字符出现的个数
        vector<int> res;

        for(int left = 0,right = 0,count = 0;right < s.size();right++)//1.控制窗口
        {
            char in = s[right];
            if(++hash2[in - 'a'] <= hash1[in - 'a'])count++;//2.进窗口+维护count
            while(right - left + 1 > p.size())//3.判断
            {
                char out = s[left++];
                if(hash2[out - 'a']-- <= hash1[out - 'a'])count--;//维护count+出窗口
            }
            if(count == p.size()) res.push_back(left);//更新结果
        }
        return res;
    }
};