題目網址：https://leetcode.cn/problems/fruit-into-baskets/

題意：有一農場種植了一排果樹, 用 fruits 表示, 其中 fruits[i] 代表第 i 棵樹的水果種類。

農場主人設立了一些規矩, 你必須按照規矩採收:

  • 你只有兩個籃子, 每個籃子只能裝單一種類的水果。每個籃子能裝的水果總量沒有限制。
  • 可以選擇任一棵樹開始採收, 你必須從每棵樹上恰摘一個水果。採收的水果須符合籃子中的水果種類。每採一次, 就要往右移動到下一棵樹繼續採收。
  • 一旦某棵樹的水果不符合籃子中的種類, 就必須停止採收。

返回可以採收的水果的最大數目。

Solution：

想法: 利用 Sliding Window

  • 先擴大窗口, 直到 window 中的種類超過 2 種（window.size() > 2）
  • 此時, 開始縮小窗口, 直到 window.size() == 2。注意：當某個種類的個數為 0 時, 要將其從 window 中移除, 不然 window.size() 無法減少
  • 跳出內層 while loop 時, 代表 window.size() == 2, 故在此處更新 res
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int left = 0, right = 0;
        int res = 0;
        unordered_map<int, int> window;

        while (right < fruits.size()) {
            ++window[fruits[right]];
            ++right;

            while (window.size() > 2) {
                if (--window[fruits[left]] == 0) { // 數量為 0 時, 要將其從 window 中移除
                    window.erase(fruits[left]);
                }
                ++left;
            }

            res = max(res, right - left);
        }

        return res;
    }
};
  • time：$O(n)$ ➔ fruits 中的元素每個最多被遍歷 2 次（left, right）
  • space：$O(1)$ ➔ window 的長度不會超過 2, 故只需常數空間