904. Fruit Into Baskets

題意

給定一個數字陣列，其中 fruits[i] 代表 $i^{th}$ 果樹的種類

題目問收集最多的水果數量為何，但有以下規則

• 你有兩個籃子，每個籃子只能放相同的水果

• 每棵樹只能拿一個水果

• 當籃子裝不下了就要停止 (第三種水果不能放進籃子)

限制

• 1 <= fruits.length <= 10^5

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

思考

根據規則，可以轉換成找出只含兩種數字的最長的 subarray ⇒ sliding window

• 維護一個 hash map 紀錄 window 中目前含有的數字個數

  • 當 subarray 延長，便將hash map 的該數字數量 + 1

    • 若該數字不存在hash map中則總數字種類 + 1

  • 當發現數字種類 > 2，便開始縮短 window 以達到條件

    • 將前端數字剃除window

      • 若某個數字記數為 1 ，代表剔除這個數字後總數會回到 < 2，因此數量 - 1 (變成 0 )，數字種類 - 1

• 每次操作後紀錄最長的數字

Solution

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        const int n = fruits.size();

        int i = 0;
        unordered_map<int, int> m;
        int count = 0;
        int ans = 0;

        for (int j = 0; j < n; j += 1) {
            if (m[fruits[j]] == 0) {
                count += 1;
            }
            m[fruits[j]] += 1;

            while (count > 2) {
                if (m[fruits[i]] == 1) {
                    count -= 1;
                }
                m[fruits[i]] -= 1;
                i += 1;
            }
            ans = max(ans, j - i + 1);
        }
        return ans;
    }
};

Time Complexity: O(N)

Space Complexity: O(N)

Optimization

• 若將歸 0 的數字從map erase，map會保持在長度 <= 3

• 透過swap，在window內將相同的數字聚集在一起，可以不需要額外空間即可知道有沒有第三種數字，空間複雜度可達 O(1)