题目

思路

思路来源于bilibili 华南溜达虎的视频讲解http://【【力扣hot100】【LeetCode 438】找到字符串中所有字母异位词｜滑动窗口】https://www.bilibili.com/video/BV1FaLaz1Eib?vd_source=05932f437c6d5e1af1e68ddc49baa55b这里只是写C++代码和思路自己复习时使用。

详细思路

创建p_map存储p中出现的元素及出现的个数。

紧接着对于s，创建双指针，移动右指针形成滑动窗口。

如果右指针指向的元素在p中出现过，加入s_map并统计出现的次数。如果该字符出现的次数在p_map和s_map中一样，count++;

当滑动窗口的长度等于p的长度时，如果此时count==p的长度，则将此时的left下标存入结果数组ans中，存储之后记录左指针的值为last，右移左指针。s_map中，last的值减一，如果last指向的值在s_map和p_map中出现的频次相等，那么count--。

如果右指针指向的元素在p中没有出现过，那么滑动窗口清零，左指针指向右指针的下一位，s_map清零（用s_map.clear()),count=0;并进入下一次循环。

最后输出ans的值。

代码

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        //创建滑动窗口 count === p.size()的是很好 
        //count pcount windows_count
        if(s.size()<p.size())
        return {};
        unordered_map<char,int>p_map;
        unordered_map<char,int>s_map;
        vector<int>ans;
        int count_1 = 0;
        int s_count = 0;
        //统计p里出现的字符频次
        for(int i = 0;i<p.size();i++)
        {
            p_map[p[i]] += 1;
        }
        //统计p中键值对的个数
        int p_count = p_map.size();
        int left = 0;
        for(int right = 0;right<s.size();right++)
        {//如果这个字符在p里出现过，加入s_map中，统计频次
            if(p_map.count(s[right]))
            {
                s_map[s[right]] += 1;
                //如果该字符在两个哈希表中的频次相等，count+=1;
                if(s_map[s[right]]==p_map[s[right]])
                s_count+=1;
                //如果滑动窗口和p的长度相等，判断count是否相等，如若相等，把当前的值加入结果数组中
                if((right-left+1)==p.size())
                {
                    if(s_count==p_count)
                    ans.push_back(left);
                    char last = s[left];
                    left++;
                    if(p_map[last]==s_map[last])
                    {
                    s_count--;
                    }
                    s_map[last]--;
                }
            }
            else
            {
            left = right+1;
            s_count=0;
            s_map.clear();
            }
        }
        return ans;
    }
};