【优选算法必刷100题】第014题（同向双指针：滑动窗口算法）：找到字符串中所有字母异位词

艾莉丝努力练剑

发布于 2025-11-17 09:15:20

1100

文章被收录于专栏：C / C++C / C++

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

力扣链接（任选一个链接做就可以了）：

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

力扣题解链接（两个题目是一样的，博主就只挂438题的题解链接了）：

滑动窗口+哈希表解决【找到字符串中所有字母异位词】问题

题目描述：

两道题是一模一样的，所以大家任选一个链接点过去做就可以了。

1.1 算法思路：滑动窗口 + 哈希表

（1）因为字符串p的异位词的长度一定与字符串p的长度相同，所以我们可以在字符串s中构造一个长度为与字符串p的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；（2）当窗口中每种字母的数量与字符串中每种字母的数量相同时，则说明当前窗口为字符串p的异位词；（3）因此可以用两个大小为26的数组来模拟哈希表，一个来保存s中的子串每个字符出现的个数，另一个来保存p中每一个字符出现的个数。这样就能判断两个串是否是异位词。

这里的算法思路比较简略，大家可以去看【博主手记】的博主手绘过程，会更好理解！

1.2 算法实现

1.2.1 第一次冲锋：失败告终

代码演示如下——

//自己实现——失败
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int hash1[30001] = { 0 };
        int hash2[30001] = { 0 };
        int ret = 0;//返回结果
        int n = s.size();
        int m = p.size();
        //左右指针
        for (int left = 0, right = 0; left < n - m + 1, right < n; left++, right++)
        {
            //进窗口
            hash2[in]++;
            //判断
            if (right - left + 1 > m)
                hash2[out]--;
        }
        //更新结果
        ret = check(hash1, hash2);
    }
    return ret;
};

为什么会失败呢？uu们可以帮博主分析一下吗？哪里出问题了？

1.2.2 优化

代码演示如下——

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        //返回结果
        vector<int> ret;
        int hash1[26] = { 0 };//统计字符串p中每个字符出现的个数
        for (auto ch : p)hash1[ch - 'a']++;//范围for

        int hash2[26] = { 0 };//统计滑动窗口中每一个字符出现的个数
        int n = s.size();
        int m = p.size();
        //左右指针
        for (int left = 0, right = 0, count = 0; right < n; right++)
        {
            char in = s[right];
             //进窗口
             hash2[in - 'a']++;
             if(hash2[in - 'a'] <= hash1[in - 'a']) count++;
             //这一步也可以优化，hash2[in - 'a']++;写进if判断里面
            if (right - left + 1 > m)//判断
            {
                char out = s[left++];//left要向右移动一位
                 if(hash2[out - 'a'] <= hash1[out -'a']) count--;
                 hash2[out - 'a']--;//也可以优化到前面，变成if(hash2[out - 'a']-- <= hash1[out -'a']) count--;
            }
            //更新结果
            if (count == m) ret.push_back(left);
        }
        return ret;
    }
};

时间复杂度：O(n)，空间复杂度：O(1)。

1.2.3 简化代码

逻辑已经对了，示例也能通过，接下来再看看代码还能不能再优化一下。我们发现其实这段代码还可以改进一下——合并两个操作：进窗口 + 维护 count、出窗口 + 维护 count——

代码演示如下——

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        //返回结果
        vector<int> ret;
        int hash1[26] = { 0 };//统计字符串p中每个字符出现的个数
        for (auto ch : p)hash1[ch - 'a']++;//范围for

        int hash2[26] = { 0 };//统计滑动窗口中每一个字符出现的个数
        int n = s.size();
        int m = p.size();
        //左右指针
        for (int left = 0, right = 0, count = 0; right < n; right++)
        {
            char in = s[right];
            // //进窗口
            // hash2[in - 'a']++;
            // if(hash2[in - 'a'] <= hash1[in - 'a']) count++;
            // //这一步也可以优化，hash2[in - 'a']++;写进if判断里面
            if (++hash2[in - 'a'] <= hash1[in - 'a']) count++;
            // 进窗口 + 维护 count
            if (right - left + 1 > m)//判断
            {
                char out = s[left++];//left要向右移动一位
                if (hash2[out - 'a']-- <= hash1[out - 'a']) count--;
                // 出窗口 + 维护count   
                // if(hash2[out - 'a'] <= hash1[out -'a']) count--;
                // hash2[out - 'a']--;//也可以优化到前面，变成if(hash2[out - 'a']-- <= hash1[out -'a']) count--;
            }
            //更新结果
            if (count == m) ret.push_back(left);
        }
        return ret;
    }
};