438找到字符串中所有字母异位词

 其实就是滑动窗口的思想,和567是一样的,固定窗口大小

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if(s.size()<p.size())return vector<int>{};
        vector<int>need(26,0);
        vector<int>have(26,0);
        vector<int>res;
        int i,len=p.size();
        for(i=0;i<p.size();i++){
            need[p[i]-'a']++;
            have[s[i]-'a']++;
        }
        if(need==have)
            res.push_back(0);
        for(i;i<s.size();i++){
            have[s[i]-'a']++;
            have[s[i-len]-'a']--;
            if(need==have)
                res.push_back(i-len+1);
        }
        return res;
    }
};

也可以只用一个数组来记录一下,使用快慢指针

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int>need(26,0);
        vector<int>res;
        for(int i=0;i<p.size();i++){
            need[p[i]-'a']++;
        }
        int fast=0,slow=0;
        while(fast<s.size()){
            need[s[fast]-'a']--;
            while(need[s[fast]-'a']<0){
                need[s[slow]-'a']++;
                slow++;
            }
            if(fast-slow+1==p.size())
            res.push_back(slow);
            fast++;
        }
        return res;
    }
};

上一篇:奇偶游戏


下一篇:LeetCode-438. 找到字符串中所有字母异位词