1. 題目鏈接：904. 水果成籃

2. 題目描述：

你正在探訪一家農(nóng)場，農(nóng)場從左到右種植了一排果樹。這些樹用一個(gè)整數(shù)數(shù)組 fruits 表示，其中 fruits[i] 是第 i 棵樹上的水果 種類 。

你想要盡可能多地收集水果。然而，農(nóng)場的主人設(shè)定了一些嚴(yán)格的規(guī)矩，你必須按照要求采摘水果：

• 你只有 兩個(gè) 籃子，并且每個(gè)籃子只能裝 單一類型 的水果。每個(gè)籃子能夠裝的水果總量沒有限制。
• 你可以選擇任意一棵樹開始采摘，你必須從 每棵 樹（包括開始采摘的樹）上 恰好摘一個(gè)水果 。采摘的水果應(yīng)當(dāng)符合籃子中的水果類型。每采摘一次，你將會(huì)向右移動(dòng)到下一棵樹，并繼續(xù)采摘。
• 一旦你走到某棵樹前，但水果不符合籃子的水果類型，那么就必須停止采摘。

給你一個(gè)整數(shù)數(shù)組 fruits ，返回你可以收集的水果的 最大 數(shù)目。

示例 1：

輸入：fruits = [1,2,1]
輸出：3
解釋：可以采摘全部 3 棵樹。

示例 2：

輸入：fruits = [0,1,2,2]
輸出：3
解釋：可以采摘 [1,2,2] 這三棵樹。
如果從第一棵樹開始采摘，則只能采摘 [0,1] 這兩棵樹。

示例 3：

輸入：fruits = [1,2,3,2,2]
輸出：4
解釋：可以采摘 [2,3,2,2] 這四棵樹。
如果從第一棵樹開始采摘，則只能采摘 [1,2] 這兩棵樹。

示例 4：

輸入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
輸出：5
解釋：可以采摘 [1,2,1,1,2] 這五棵樹。

提示：

• 1 <= fruits.length <= 105
• 0 <= fruits[i] < fruits.length

3. 解法（滑動(dòng)窗口）

3.1 算法思路：

求一段連續(xù)的空間，使用滑動(dòng)窗口思想

讓滑動(dòng)窗口滿足：窗口內(nèi)水果的種類只有兩種

做法：右端水果進(jìn)入窗口的時(shí)候，用哈希表統(tǒng)計(jì)這個(gè)水果的頻次。這個(gè)水果進(jìn)來后，判斷哈希表的大小：

• 如果大小超過2：說明窗口內(nèi)水果種類超過了兩種。那么就從左側(cè)開始依次將水果劃出窗口，直到哈希表的大小小于等于2，然后更新結(jié)果
• 如果沒有超過2，說明當(dāng)前窗口水果的種類不超過兩種，直接更新結(jié)果ret

3.2 算法流程：

• 初始化哈希表hash來統(tǒng)計(jì)窗口內(nèi)水果的種類和數(shù)量；
• 初始化變量：左右指針left=0，right=0，記錄結(jié)果的變量ret=0；
• 當(dāng)right小于數(shù)組大小的時(shí)候，一直執(zhí)行下列循環(huán)：
  • 將當(dāng)前水果放入哈希表中
  • 判斷當(dāng)前水果進(jìn)來后，嘻哈表的大小：
    • 如果超過2：
      • 將左側(cè)元素滑出窗?，并且在哈希表中將該元素的頻次減?；
      • 如果這個(gè)元素的頻次減?之后變成了 0，就把該元素從哈希表中刪除；
      • 重復(fù)上述兩個(gè)過程，直到哈希表中的??不超過 2；
  • 更新結(jié)果ret
  • right++，讓下一個(gè)元素進(jìn)入窗口
• 循環(huán)結(jié)束后，ret存的就是最終結(jié)果

3.3 C++算法代碼：

class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100001]={0};//統(tǒng)計(jì)窗口出現(xiàn)了多少種水果int ret=0;for(int left=0,right=0,kinds=0;right<fruits.size();right++){if(hash[fruits[right]]==0) kinds++;//維護(hù)水果的種類hash[fruits[right]]++;//進(jìn)窗口while(kinds>2)//判斷{//出窗口hash[fruits[left]]--;if(hash[fruits[left]]==0) kinds--;left++;}ret=max(ret,right-left+1);}return ret;}
};