艺术字体在线生成器免费转换器_推广普通话宣传周活动方案_网站建设方案书模板_seo零基础培训

题目链接：

904.水果成篮

---

---

题目描述：

---

解法

解法一：暴力枚举+哈希表

找到所有的子数组，然后比较大小。

解法二：滑动窗口+哈希表

本质上就是在数组中找到最长的一个子数组，子数组里面不超过两种水果。

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

kinds有两种情况：

1. kinds不变

   若当前区间满足kinds=2，那么left向右移动，有可能仍然包含两种水果。

   此时，right不需要后移

2. kinds变小

   若当前区间满足kinds=2，那么left向右移动，有可能只包含一种水果。

   此时，right需要后移

解法：

1. left=0，right=0
2. 进窗口
3. 判断，出窗口
4. 更新结果

• 如果大小超过 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]

1. left = 0, right = 0

2. f[0]是1类型的果树，hash[f[0]]++后等于1，说明在当前窗口中，水果类型为1的出现次数为1次。

   hash.size()=1，ret = max(ret, right - left + 1)=1，right++

3. f[1]是2类型的果树，hash[f[1]]++后等于1，说明在当前窗口中，水果类型为2的出现次数为1次。

   hash.size()=2,ret = max(ret, right - left + 1)=2，right++

4. f[2]是1类型的果树，hash[f[2]]++后等于2，说明在当前窗口中，水果类型为1的出现次数为2次。

   hash.size()=2,ret = max(ret, right - left + 1)=3，right++

5. f[3]是2类型的果树，hash[f[3]]++后等于2，说明在当前窗口中，水果类型为2的出现次数为2次。

   hash.size()=2,ret = max(ret, right - left + 1)=4，right++

6. 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++

7. 后面步骤差不多，不过多赘述了。