在一排樹(shù)中，第 i 棵樹(shù)產(chǎn)生 tree[i] 型的水果。
你可以從你選擇的任何樹(shù)開(kāi)始，然后重復(fù)執(zhí)行以下步驟：

把這棵樹(shù)上的水果放進(jìn)你的籃子里。如果你做不到，就停下來(lái)。
移動(dòng)到當(dāng)前樹(shù)右側(cè)的下一棵樹(shù)。如果右邊沒(méi)有樹(shù)，就停下來(lái)。
請(qǐng)注意，在選擇一顆樹(shù)后，你沒(méi)有任何選擇：你必須執(zhí)行步驟 1，然后執(zhí)行步驟 2，然后返回步驟 1，然后執(zhí)行步驟 2，依此類推，直至停止。

你有兩個(gè)籃子，每個(gè)籃子可以攜帶任何數(shù)量的水果，但你希望每個(gè)籃子只攜帶一種類型的水果。
用這個(gè)程序你能收集的水果總量是多少？

示例 1：

輸入：[1,2,1]
輸出：3
解釋：我們可以收集 [1,2,1]。
示例 2：

輸入：[0,1,2,2]
輸出：3
解釋：我們可以收集 [1,2,2].
如果我們從第一棵樹(shù)開(kāi)始，我們將只能收集到 [0, 1]。
示例 3：

輸入：[1,2,3,2,2]
輸出：4
解釋：我們可以收集 [2,3,2,2].
如果我們從第一棵樹(shù)開(kāi)始，我們將只能收集到 [1, 2]。
示例 4：

輸入：[3,3,3,1,2,1,1,2,3,3,4]
輸出：5
解釋：我們可以收集 [1,2,1,1,2].
如果我們從第一棵樹(shù)或第八棵樹(shù)開(kāi)始，我們將只能收集到 4 個(gè)水果。

解題思路

這題其實(shí)要求其實(shí)很簡(jiǎn)單，就是找出數(shù)組中長(zhǎng)度最大的連續(xù)由2種元素構(gòu)成的子數(shù)組，返回這個(gè)子數(shù)組的長(zhǎng)度。但由于本題有時(shí)間限制，只是樸素的解法會(huì)出現(xiàn)超時(shí)的情況，需要對(duì)實(shí)現(xiàn)進(jìn)行一定的優(yōu)化。

參考花花醬的hashtable+ sliding windows

花花醬解法

class Solution {
public:
// 樸素解法
    int totalFruit(vector<int>& tree) {
        int size = tree.size();
        int fruit[size] = {0};
        int max =0;
        
        for(int i = 0; i< size;i++){
            int number = 1;
            int type1 = -1;
            // 第一種水果
            type1 = tree[i];
            int type2 = -1;
            for(int j = i+1; j<size ;j++){
                // 第二種水果
                if(tree[j]!=tree[i]){
                    // type2 is null
                    if(type2 < 0){
                        type2 = tree[j];
                        number++;
                    }else{
                        // 出現(xiàn)第三種水果，跳出循環(huán)
                        if(tree[j] != type2){
                            break;
                        }else{
                            number++;
                        }
                    }
                    
                }else{
                    number++;
                }
            }
            fruit[i] = number;
            if(number> max)
                max = number;
        }
        return max;
    }
    
   
public:
// by [花花醬] (https://zxi.mytechroad.com/blog/hashtable/leetcode-904-fruit-into-baskets/)

  int totalFruit(vector<int>& tree) {        
    map<int, int> idx; // {fruit -> last_index}
    int ans = 0;
    int cur = 0;
    for (int i = 0; i < tree.size(); ++i) {
      int f = tree[i]; // 取一種水果
      if (!idx.count(f)) { // 返回值只有0或1
         // !idx.count(f) ==  1,即出現(xiàn)某種新水果時(shí)
        if (idx.size() == 2) { // 如果已經(jīng)有了兩種水果，再出現(xiàn)第三種水果的時(shí)候
          auto it1 = begin(idx); 
          auto it2 = next(it1);
          if (it1->second > it2->second) swap(it1, it2);
          // 找到之前兩種水果中，下標(biāo)最小的水果，開(kāi)始新的窗口
          cur = i - it1->second - 1; // cur存新窗口的大小       
          idx.erase(it1); // 刪除下標(biāo)較小的水果
        }       
      }   
      // 添加新水果的下標(biāo)信息
      idx[f] = i;  
      // 比較新窗口和上一個(gè)窗口的大小
      ans = max(++cur, ans);
    }
    return ans;
  }

};