AC截图

题目

思路

我一开始是打算将窗口内的s子字符串和p字符串都重新排序，然后判断是否相等，再之后进行窗口滑动。不过缺点是会超时。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> vec;

        if(s.size()<p.size()){
            return vec;
        }


        int len=p.size();
        sort(p.begin(),p.end());

        for(int i=0;i<=s.size()-len;i++){
            string ss = s.substr(i,len);
            sort(ss.begin(),ss.end());
            if(p==ss){
                vec.push_back(i);
            }
        }
        return vec;
    }
};

后面改用滑动窗口，

因为字符串 p 的异位词的长度一定与字符串 p 的长度相同，所以我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p 的异位词。

关键部分在此：

    //开始让窗口进行滑动
    for(int i=0;i<sLen-pLen;i++){ //i是滑动前的首位
        --scount[s.charAt(i) -'a'];       //将滑动前首位的词频删去
        ++scount[s.charAt(i+pLen) -'a'];  //增加滑动后最后一位的词频（以此达到滑动的效果）

        //判断滑动后处，是否有异位词
        if(scount==pcount){
            vec.push_back(i+1);
        } 
    }

代码

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> vec;

        if(s.size()<p.size()){
            return vec;
        }


        int plen=p.size();
        int slen=s.size();
        
        vector<int> scount(26);
        vector<int> pcount(26);
        for(int i=0;i<plen;i++){
            pcount[p[i]-'a']++;
            scount[s[i]-'a']++;
        }
        if(scount==pcount){
            vec.push_back(0);
        }

        for(int i=0;i<slen-plen;i++){
            scount[s[i]-'a']--;
            scount[s[i+plen]-'a']++;

            if(scount==pcount){
                vec.push_back(i+1);
            }
        }

        return vec;
    }
};