题目链接:
904.水果成篮
文章目录
- 题目链接:
- 题目描述:
- 解法
- C++ 算法代码:
- 图解
题目描述:
解法
解法一:暴力枚举+哈希表
找到所有的子数组,然后比较大小。
解法二:滑动窗口+哈希表
本质上就是在数组中找到最长的一个子数组,子数组里面不超过两种水果。
当右端水果进入窗口的时候,用哈希表统计这个水果的频次。这个水果进来后,判断哈希表的大小。
kinds
有两种情况:
kinds
不变若当前区间满足
kinds=2
,那么left
向右移动,有可能仍然包含两种水果。此时,
right
不需要后移
kinds变小
若当前区间满足
kinds=2
,那么left
向右移动,有可能只包含一种水果。此时,
right
需要后移
解法:
left=0,right=0
- 进窗口
- 判断,出窗口
- 更新结果
如果大小超过
2
:说明窗口内水果种类超过了两种。那么就从左侧开始依次将水果划出窗口,直到哈希表的大小小于等于2
,然后更新结果;如果没有超过
2
:说明当前窗口内水果的种类不超过两种,直接更新结果ret
。
C++ 算法代码:
class Solution
{public:int totalFruit(vector<int>& f) {unordered_map<int, int> hash; // 使用哈希表(unordered_map)统计窗口内出现了多少种水果int ret = 0;for(int left = 0, right = 0; right < f.size(); right++){hash[f[right]]++; // 将当前水果类型 f[right] 添加到哈希表中,并更新其计数//f[right] 表示当前遍历到的水果类型//hash[f[right]]:这部分代码访问哈希表 hash 中键为 f[right] 的元素。例如,hash[1] 表示水果类型 1 在当前窗口内的出现次数。//hash[f[right]]++:这行代码将 hash[f[right]] 的值增加 1。这意味着在当前窗口中,水果类型 f[right] 的出现次数增加了一次。while(hash.size() > 2) // 如果哈希表的大小超过 2,意味着当前窗口内包含超过两种水果类型{// 从当前窗口的左边界移除水果类型 f[left]hash[f[left]]--;if(hash[f[left]] == 0)// 如果该水果类型的计数为 0,则从哈希表中移除该键hash.erase(f[left]);left++;// 移动左边界指针 left,向右移动以缩小窗口}ret = max(ret, right - left + 1);// 更新结果 ret 为当前窗口长度与之前记录的最大长度中的较大值// 窗口长度计算为 right - left + 1}return ret;}
};
图解
例如:f=[1,2,1,2,3,2,3,3]
left = 0, right = 0
-
f[0]
是1
类型的果树,hash[f[0]]++
后等于1
,说明在当前窗口中,水果类型为1
的出现次数为1
次。hash.size()=1
,ret = max(ret, right - left + 1)=1
,right++
-
f[1]
是2
类型的果树,hash[f[1]]++
后等于1
,说明在当前窗口中,水果类型为2
的出现次数为1
次。hash.size()=2
,ret = max(ret, right - left + 1)=2
,right++
-
f[2]
是1
类型的果树,hash[f[2]]++
后等于2
,说明在当前窗口中,水果类型为1
的出现次数为2
次。hash.size()=2
,ret = max(ret, right - left + 1)=3
,right++
-
f[3]
是2
类型的果树,hash[f[3]]++
后等于2
,说明在当前窗口中,水果类型为2
的出现次数为2
次。hash.size()=2
,ret = max(ret, right - left + 1)=4
,right++
-
f[4]
是3
类型的果树,hash[f[4]]++
后等于1
,说明在当前窗口中,水果类型为3
的出现次数为1
次。hash.size()=3>2
进入循环。hash[f[left]]--;
// 从当前窗口的左边界移除水果类型f[left]
此时
hash[1类型的果树]=1
,继续hash[f[left]]--;
此时
hash[2类型的果树]=1
,继续hash[f[left]]--;
此时
hash[1类型的果树]=0
,执行if(hash[f[left]] == 0),hash.erase(f[left]);
ret = max(ret, right - left + 1)=4
,right++
- 后面步骤差不多,不过多赘述了。