算法每日双题精讲 —— 滑动窗口（水果成篮，找到字符串中所有字母异位词）

🌟快来参与讨论💬，点赞👍、收藏⭐、分享📤，共创活力社区。 🌟

别再犹豫了！快来订阅我们的算法每日双题精讲专栏，一起踏上算法学习的精彩之旅吧！💪

今天，咱们就一同来探究 “水果成篮” 和 “找到字符串中所有字母异位词” 这两道经典题目，看看滑动窗口算法是如何在其中施展魔法的🧙‍♂️。

---

目录

💯水果成篮

📖题目描述

🧠讲解算法原理

💻代码实现（以 C++ 为例）

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

📖题目描述

 🧠讲解算法原理

 💻代码实现（以 C++ 为例）

---

💯水果成篮

题目链接👉【力扣】

📖题目描述

根据示例分析，该题的本质就是：找出最长子数组的长度，子数组不超过俩种水果类型

🧠讲解算法原理

解法一：

 我们用暴力解法写一下，例如f=[1,2,3,2,2]

依次找出所以的情况👇

1.  

代码中我们利用哈希表列举情况，用哈希表统计水果出现的类型数

解法二：

先分析

 当我们用暴力解法时，遇到如下情况👇，我们让 left++ ，right 回到 left的位置，继续列举情况

当left++时，区间的 kinds 要么不变，要么减少一个

• 当kinds不变时，right没有必要改变
• 当kinds减少时，right可以继续向后移动

 因此我们可以用滑动窗口的解法，right不回退嘛

滑动窗口四大步：

1.  left=0,right=0
2. 进窗口——right右移动的时候
3. 判断    出窗口——就是left右移动的时候
4. 更新结果

举例： f=[1，2，1，2，3，2，3，3]

每次遍历right,让其放入hash表里面，判断有没有超出类型个数

当hash.length>2时出窗口

left右移动的时候，要根据某个水果种类的数量来进行移动，因此我们创建的hash表要有俩个参数，一个记录种类，一个记录个数

例如下面👇，我们要将left移动到3的前面

💻代码实现（以 C++ 为例）

class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100001]={0};//统计窗口内出现了多少种结果int ret=0;for(int left=0,right=0,kinds=0;right<fruits.size();right++){if(hash[fruits[right]]==0) kinds++;hash[fruits[right]]++;//进窗口while(kinds>2)//判断{//出窗口hash[fruits[left]]--;if(hash[fruits[left]]==0)   kinds--;left++;}ret=max(ret,right-left+1);}return ret;}
};

---

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

题目链接👉【力扣】

📖题目描述

 

 🧠讲解算法原理

1.如何判断俩个字符串是否是异位词？

• 可以先排序再比较，但是时间复杂度为nlogn ，比较大
• 通过统计字符串中字符出现的个数也可以判断，借助hash表即可

 2.解决问题

例如

暴力解法： 

计入p的长度m ，在S里依次比较 

 

优化解法：

当字符串依次遍历时， ，我们发现ba重复出现，所以我们只要将c从hash表移除，让e加入hash表即可，滑动窗口

 

滑动窗口四大步：

1.  left=0,right=0
2. 进窗口——right右移动的时候
3. 判断    出窗口——就是left右移动的时候
4. 更新结果

 

3.优化：更新结果的判断条件

利用变量count来统计窗口中“有效字符”的个数

使用一个数组targetCount来记录字符串p中每个字母的出现次数，再使用一个数组windowCount来记录当前窗口内每个字母的出现次数。设一个变量valid来表示窗口内有效字母的数量，初始值为0。 

然后，将right指针向右移动，每移动一次，就将新字母在windowCount中的计数加1，并检查该字母的计数是否等于在targetCount中的计数，如果相等，则valid加1。当valid等于p中不同字母的数量时，说明当前窗口是一个字母异位词。

 

此时，将left指针向右移动，同时更新windowCount和valid，直到valid小于p中不同字母的数量。在移动left指针的过程中，如果窗口内的子串长度等于p的长度，就将left指针的索引加入到结果数组中。

 

重复上述步骤，直到right指针走到字符串s的末尾。最后，返回结果数组。

 💻代码实现（以 C++ 为例）

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> result;// 如果s的长度小于p的长度，直接返回空结果if (s.length() < p.length()) return result;// 用于记录字符串p中每个字母的出现次数vector<int> targetCount(26, 0);// 用于记录当前窗口内每个字母的出现次数vector<int> windowCount(26, 0);int valid = 0;// 初始化targetCount数组for (char c : p) {targetCount[c - 'a']++;}int left = 0, right = 0;while (right < s.length()) {int rightIndex = s[right] - 'a';// 将新字母在windowCount中的计数加1windowCount[rightIndex]++;// 如果该字母的计数小于等于在targetCount中的计数，说明该字母在窗口内的数量还未超过p中该字母的数量，有效字母数量加1if (windowCount[rightIndex] <= targetCount[rightIndex]) {valid++;}// 当窗口大小大于p的长度时，移动left指针缩小窗口while (right - left + 1 > p.length()) {int leftIndex = s[left] - 'a';// 将left指针指向的字母在windowCount中的计数减1windowCount[leftIndex]--;// 如果该字母的计数小于在targetCount中的计数，说明该字母在窗口内的数量已经小于p中该字母的数量，有效字母数量减1if (windowCount[leftIndex] < targetCount[leftIndex]) {valid--;}left++;}// 如果有效字母数量等于p中不同字母的数量，说明当前窗口是一个字母异位词，将left指针的索引加入结果数组if (valid == p.length()) {result.push_back(left);}right++;}return result;}
};

---

我以后还会对 算法 相关知识进行更多的创作，欢迎大家关注我，一起探索 算法 的奇妙世界😜

👉【A Charmer】