力扣-438题找到字符串中所有字母异位词（C++）- 滑动窗口，类似力扣第三题

快来打我* 2022-09-07 03:51 112阅读 0赞

题目链接：[https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/][https_leetcode-cn.com_problems_find-all-anagrams-in-a-string]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]

class Solution {
        
    public:
        vector<int> findAnagrams(string s, string p) {
        
            vector<int> result;
            unordered_map<int,int> umap;
            for(auto e:p) umap[e]++;
    
            int valid=0,total=umap.size();
            for(int i=0,j=0;i<s.size();++i){
        //左边每移除一个字符就++，右边每出现一个字符就--
                umap[s[i]]--;
                if(umap[s[i]]==0) valid++;
    
                while(i-j+1>p.size()){
        
                    if(umap[s[j]]==0) valid--;
                    umap[s[j]]++;//因为左边每移动一次，相对应的数量是+1的
                    j++;
                }
    
                if(valid==total) result.push_back(j);
            }
    
            return result;
    
        }
    };

[https_leetcode-cn.com_problems_find-all-anagrams-in-a-string]: https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20220829/080a4dfcef4c4d119d5c5f51d5bf7c28.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]: /images/20220829/3f941f37516947c6b73a5694483e02a7.png