904. Fruit Into Baskets

題目連結: 904. Fruit Into Baskets

題目描述

在一排果樹中，每棵樹上都有一種水果，編號為 fruits[i]。你有兩個籃子，每個籃子只能放一種水果，但每個籃子可以放無限多個該種水果。

你可以從果樹的任意位置開始採摘，但一旦開始，就必須一直往前，不能回頭。你需要找到一段最長的連續子陣列，使得其中包含的水果種類不超過兩種，並返回該子陣列的長度。

限制條件：

• 1 <= fruits.length <= 10^5
• 0 <= fruits[i] < fruits.length

解題思路

這個問題可以轉化為在一個整數陣列中，找到包含最多兩種不同數字的最長連續子陣列的長度。這是一個典型的滑動視窗（Sliding Window）問題。

主要步驟

1. 初始化：
   • 使用兩個指標 i 和 j，分別代表視窗的左端和右端。
   • 使用一個雜湊表（unordered_map）m，用於記錄視窗中每種水果的數量。
   • 使用變數 count，記錄視窗中不同水果的種類數。
   • 使用變數 ans，記錄目前為止找到的最長子陣列長度。
2. 擴展視窗：
   • 遍歷陣列 fruits，右指標 j 從 0 遍歷到 n - 1。
   • 將當前水果 fruits[j] 的數量在雜湊表中加一。
   • 如果該水果是新種類（即數量從 0 增加到 1），則將 count 加一。
3. 收縮視窗：
   • 當 count > 2（即視窗中有超過兩種水果）時，需要收縮視窗：
     • 減少左端水果 fruits[i] 的數量。
     • 如果某種水果的數量減少到 0，將 count 減一。
     • 左指標 i 右移一位。
4. 更新答案：
   • 在每次擴展視窗後，更新 ans = max(ans, j - i + 1)，記錄最大的子陣列長度。

程式碼

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;
    }
};

時間與空間複雜度分析

時間複雜度：O(n)

• 解釋：
  • 變數 n 為陣列 fruits 的長度。
  • 雖然外部有一個 for 迴圈，內部有一個 while 迴圈，看似是二重迴圈，但實際上每個元素最多被加入和移出視窗一次。
  • 指標 j 和 i 最多各自遍歷整個陣列一次，因此總時間複雜度為線性 O(n)。

空間複雜度：O(1)

• 解釋：
  • 雖然使用了雜湊表 m，但其中最多只會存儲兩種水果的種類（鍵值對）。
  • count 變數的最大值為 2。
  • 因此，使用的額外空間是常數級別的，為 O(1)。

優化方案

優化空間複雜度至 O(1)

• 思路：
  • 由於我們只需要追蹤兩種水果，我們可以使用兩個變數來記錄這兩種水果的類型，以及它們最後出現的位置。
  • 在遍歷陣列時，當遇到第三種水果時，更新左指標 i，將視窗縮小到只包含當前的兩種水果。
• 實現：
  • 使用兩個變數 fruit1 和 fruit2，以及對應的最後出現位置 last1 和 last2。
  • 每次更新後，計算當前視窗的長度，更新答案。
• 優點：
  • 不再需要使用雜湊表，空間複雜度降低到常數級別。
  • 由於只需追蹤兩種水果，程式邏輯更為簡潔。