《算法题讲解指南：优选算法-滑动窗口》--13 水果成篮

🔥小叶-duck：个人主页

❄️个人专栏：《Data-Structure-Learning》

《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--从优选到贪心

✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游

目录

13 水果成篮

题目链接：

​编辑

题目示例：

解法（滑动窗口）：

算法思路：

算法流程：

C++代码演示：方法一(使用容器)

C++代码演示：方法二(用数组模拟哈希表)

算法总结及流程解析：

结束语

13 水果成篮

题目链接：

题目示例：

解法（滑动窗口）：

算法思路：

      研究的对象是一段连续的区间，可以使用【滑动窗口】思想来解决问题。

      让滑动窗口满足：窗口内水果的种类只有两种。

      做法：右端水果进入窗口的时候，用哈希表统计这个水果的频次。这个水果进来后，判断哈希表的大小

• 如果大小超过 2：说明窗口内水果种类超过了两种。那么就从最左侧开始依次将水果划出窗口，直到哈希表的大小小于 2 ，然后更新结果；
• 如果没有超过 2 ，说明当前窗口内水果的种类不超过两种，直到更新结果 len。

算法流程：

  1.初始化哈希表 hash 来统计窗口内水果的种类和数量；

  2.初始化变量：左右指针 left = 0，right = 0，记录结果的变量 len = 0；

  3.当 right 小于数组大小的时候，一直执行下列循环：

• 将当前水果放入哈希表
• 判断当前水果进来后，哈希表的大小：

            如果超过 2：

                        将左侧元素滑出窗口，并且在哈希表中将该元素的频次减一；

                        如果这个元素的频次减一之后变成了 0，就把该元素从哈希表中删除；

                        重复上述两个过程，直到哈希表中的大小不超过 2；

• 更新结果 len；
• right++，让下一个元素进入窗口；

  4.循环结束后， len 存的就是最终结果。

C++代码演示：方法一(使用容器)

class Solution { public: int totalFruit(vector<int>& fruits) { //方法一：使用容器(如果对哈希掌握不是很好可以看下面方法二) unordered_map<int ,int> hash; //统计窗口内出现水果的种类 int left = 0; int right = 0; int len = 0; for(right = 0; right < fruits.size(); right++) { hash[fruits[right]]++; //进窗口 while(hash.size() > 2) //判断 { hash[fruits[left]]--; //出窗口 if(hash[fruits[left]] == 0) { hash.erase(fruits[left]); } left++; } len = max(len, right - left + 1); //更新结果 } return len; } };

C++代码演示：方法二(用数组模拟哈希表)

class Solution { public: int totalFruit(vector<int>& fruits) { //方法二：用数组模拟哈希表(只需要了解哈希可以对数据存放的次数进行计数即可) int hash[100001] = { 0 };//根据题目提示可知水果种类最多不超过100000 int left = 0; int right = 0; int len = 0; int kinds = 0; //用一个新变量来维护水果种类 for(right = 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++; } len = max(len, right - left + 1); //更新结果 } return len; } };

算法总结及流程解析：

结束语

       到此，13 水果成篮 这道算法题就讲解完了。通过滑动窗口处理连续区间问题。当窗口内水果种类超过2种时，左指针右移调整窗口，利用哈希表统计频次，最终求出最大区间长度。提供C++两种实现：容器版和数组模拟哈希表版。希望大家能有所收获！