算法每日双题精讲 —— 滑动窗口（水果成篮，找到字符串中所有字母异位词）
🌟快来参与讨论💬，点赞👍、收藏⭐、分享📤，共创活力社区。 🌟
别再犹豫了！快来订阅我们的算法每日双题精讲专栏，一起踏上算法学习的精彩之旅吧！💪
今天，咱们就一同来探究 “水果成篮” 和 “找到字符串中所有字母异位词” 这两道经典题目，看看滑动窗口算法是如何在其中施展魔法的🧙♂️。
目录
💯水果成篮
📖题目描述
🧠讲解算法原理
💻代码实现（以 C++ 为例）
💯找到字符串中所有字母异位词
📖题目描述
🧠讲解算法原理
💻代码实现（以 C++ 为例）
💯水果成篮
题目链接👉【力扣】
📖题目描述
根据示例分析，该题的本质就是：找出最长子数组的长度，子数组不超过俩种水果类型
🧠讲解算法原理
解法一：
我们用暴力解法写一下，例如f=[1,2,3,2,2]
依次找出所以的情况👇
代码中我们利用哈希表列举情况，用哈希表统计水果出现的类型数
解法二：
先分析
当我们用暴力解法时，遇到如下情况👇，我们让 left++ ，right 回到 left的位置，继续列举情况
当left++时，区间的 kinds 要么不变，要么减少一个
- 当kinds不变时，right没有必要改变
- 当kinds减少时，right可以继续向后移动
因此我们可以用滑动窗口的解法，right不回退嘛
滑动窗口四大步：
- left=0,right=0
- 进窗口——right右移动的时候
- 判断 出窗口——就是left右移动的时候
- 更新结果
举例： 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表即可，滑动窗口
滑动窗口四大步：
- left=0,right=0
- 进窗口——right右移动的时候
- 判断 出窗口——就是left右移动的时候
- 更新结果
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】
