【做一道算一道】找到字符串中所有字母异位词

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

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

示例 2:
输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

思路

好久没写前面这些，思路怪怪的，记一下。
显然p比s大的时候，没有子串可言。
自己想了个歪七扭八的思路，算双指针吧，想用string来记p，在遍历过程中删减string，空了就判断并添加初始坐标，发现不存在的，就重置。应该是过程太啰嗦了，最后超时了，不过应该是能行的，就当熟练一些函数吧。
正常的思路应该是滑动窗口，哈希记下词频，更新哈希并维持窗口，双指针的差值等于p长度就记录。

代码

我的超时：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res1;
        unordered_set<int> res;
        string temp=p;

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

        for(int i=0,j=0;j<=s.size();){
            if(temp.find(s[j])!=string::npos){
                temp.erase(temp.find(s[j]),1);
                ++j;
            }else if(temp.empty()){
                temp=p;
                res.insert(i);
                ++i;
                j=i;
            }else{
                temp=p;
                ++i;
                j=i;
            }
        }
        res1.assign(res.begin(),res.end());
        return res1;
    }
};

滑动窗口：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if(s.size()<p.size())
        return {};

        vector<int> res;
        int alp[27];
        for(char i:p){
            ++alp[i-'a'];
        }

        for(int left=0,right=0;right<s.size();++right){
            --alp[s[right]-'a'];
            while(alp[s[right]-'a']<0){
                ++alp[s[left]-'a'];
                ++left;
            }
            if(right-left+1==p.size()){
                res.emplace_back(left);
            }
        }
    return res;
    }
};