【力扣】438.找到字符串中所有字母异位词

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;}
};