《算法闯关指南：优选算法--滑动窗口》--13水果成篮
《算法闯关指南：优选算法--滑动窗口》--13水果成篮
🔥草莓熊Lotso：个人主页
❄️个人专栏：《C++知识分享》《Linux 入门到实践：零基础也能懂》
✨生活是默默的坚持，毅力是永久的享受。
🎬博主简介：
前言：
聚焦算法题实战，系统讲解三大核心板块：优选算法：剖析动态规划、二分法等高效策略，学会寻找“最优解”。 递归与回溯：掌握问题分解与状态回退，攻克组合、排列等难题。 贪心算法：理解“局部最优”到“全局最优”的思路，解决区间调度等问题 内容以题带点，讲解思路与代码实现，帮助大家快速提升代码能力。
水果成篮
题目链接：
题目描述：
题目示例：
解法（滑动窗口）：
算法思路：
研究的对象是一段连续的区间，可以使用【滑动窗口】思想来解决问题。
让滑动窗口满足：窗口内水果的种类只有两种。
做法：右端水果进入窗口的时候，用哈希表统计这个水果的频次。这个水果进来后，判断哈希表的大小
- 如果大小超过 2 ：说明窗口内水果种类超过了两种。那么就从最左侧开始依次将水果划出窗口，直到哈希表的大小小于 2 ，然后更新结果；
- 如果没有超过 2 ，说明当前窗口内水果的种类不超过两种，直到更新结果 ret。
算法流程：
1.初始化哈希表 hash 来统计窗口内水果的种类和数量；
2.初始化变量：左右指针 left=0，right=0，记录结果的变量 ret=0；
3.当 right 小于数组大小的时候，一直执行下列循环：
- 将当前水果放入哈希表
- 判断当前水果进来后，哈希表的大小：
如果超过 2 ：
将左侧元素滑出窗口，并且在哈希表中将该元素的频次减一；
如果这个元素的频次减一之后变成了 0，就把该元素从哈希表中删除；
重复上述两个过程，直到哈希表中的大小不超过 2；
- 更新结果 ret；
- right++，让下一个元素进入窗口；
4.循环结束后， ret 存的就是最终结果。
C++代码演示：(使用容器)
class Solution {
public:
int totalFruit(vector<int>& fruits) {
//数据范围有限可以使用数组模拟哈希表
int hash[100001]={0};//后面需要加个kinds变量
int n=fruits.size();
int left=0,right=0,len=0;
while(right<n)
{
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);
right++;
}
return len;
}
};C++代码演示：(用数组模拟哈希表)
class Solution {
public:
int totalFruit(vector<int>& fruits) {
//数据范围有限可以使用数组模拟哈希表
int hash[100001]={0};//后面需要加个kinds变量
int n=fruits.size();
int left=0,right=0,kinds=0,len=0;
while(right<n)
{
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);
right++;
}
return len;
}
};算法总结&&笔记展示：
笔记字有点丑，大家见谅：
往期回顾：
《算法闯关指南：优选算法--滑动窗口》--09长度最小的子数串，10无重复字符的最长字串
《算法闯关指南：优选算法--滑动窗口》--11最大连续1的个数 III，12将 x 减到 0 的最小操作数
结语：本篇博客通过滑动窗口处理连续区间问题。当窗口内水果种类超过2种时，左指针右移调整窗口，利用哈希表统计频次，最终求出最大区间长度。提供C++两种实现：容器版和数组模拟哈希表版，并附算法思路图解。如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。
✨把这些内容吃透超牛的！放松下吧✨ ʕ˘ᴥ˘ʔ づきらど
腾讯云开发者
