【优选算法必刷100题】第014题（同向双指针：滑动窗口算法）：找到字符串中所有字母异位词
🔥艾莉丝努力练剑：个人主页
❄专栏传送门：《C语言》、《数据结构与算法》、C/C++干货分享&学习过程记录、Linux操作系统编程详解、笔试/面试常见算法：从基础到进阶
⭐️为天地立心，为生民立命，为往圣继绝学，为万世开太平
🎬艾莉丝的简介：
🎬艾莉丝的算法专栏简介：
目录
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; } };时间复杂度：O(n)，空间复杂度：O(1)。
现在耗时的情况就已经优化不少了。
1.3 博主手记
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己推导很重要！
这个手记前面的部分包括暴力解法、直接比较hash1 == hash2的解法这两个方法博主在本文中都没有演示，大家可以根据自己的理解来动手实操一下！
结尾
往期回顾：
【优选算法必刷100题】第013题（同向双指针：滑动窗口算法）：水果成篮问题
结语：都看到这里啦！那请大佬不要忘记给博主来个“一键四连”哦！
🗡博主在这里放了一只小狗，大家看完了摸摸小狗放松一下吧！🗡
૮₍ ˶ ˊ ᴥ ˋ˶₎ა
