904. Fruit Into Baskets

Medium
Description

給定整數陣列 fruits（代表一排果樹的水果種類），你有兩個籃子，每個籃子只能放一種水果。從任一棵樹開始連續採集，遇到第三種水果就停止。回傳最多能採集的水果數量。

Example:

Input: fruits = [1,2,1,2,3] Output: 4（子陣列 [1,2,1,2] 只有兩種水果）

Intuition#

核心思路：本質是「最長的最多包含 2 種不同元素的連續子陣列」，用滑動視窗 + HashMap 維護種類計數。

  • 兩個籃子 = 最多兩種不同水果
  • 經典的「最多 k 種不同元素的最長子陣列」模板，這裡 k = 2
  • HashMap 記錄視窗內每種水果的數量，超過 2 種時收縮左邊界

Approaches#

1: Brute Force#

  • 概念: 嘗試每個起點，向右延伸直到超過 2 種水果
  • 時間複雜度: O(n²)
  • 空間複雜度: O(1) - 最多追蹤 3 種
Brute Force 程式碼
class Solution {
    fun totalFruit(fruits: IntArray): Int {
        var result = 0
        for (i in fruits.indices) {
            val types = mutableSetOf<Int>()
            var j = i
            while (j < fruits.size) {
                types.add(fruits[j])
                if (types.size > 2) break
                j++
            }
            result = maxOf(result, j - i)
        }
        return result
    }
}

⭐2: Sliding Window + HashMap#

  • 概念: 右指針擴展視窗，用 HashMap 記錄各水果數量；當種類 > 2 時，收縮左邊界直到種類 <= 2
  • 時間複雜度: O(n) - 左右指針各遍歷一次
  • 空間複雜度: O(1) - HashMap 最多 3 個 entry
class Solution {
    fun totalFruit(fruits: IntArray): Int {
        val count = mutableMapOf<Int, Int>()
        var left = 0
        var result = 0

        for (right in fruits.indices) {
            count[fruits[right]] = (count[fruits[right]] ?: 0) + 1

            while (count.size > 2) {
                val leftFruit = fruits[left]
                count[leftFruit] = count[leftFruit]!! - 1
                if (count[leftFruit] == 0) count.remove(leftFruit)
                left++
            }

            result = maxOf(result, right - left + 1)
        }
        return result
    }
}

HashMap 中計數歸零時要立即 remove，否則 count.size 不會正確反映種類數。

🔑 Takeaways#

  • Pattern: 可變大小滑動視窗 + HashMap 計數（At Most K Distinct 模板）
  • 關鍵技巧: 此題是「最多 k 種不同元素的最長子陣列」的特例（k=2），同樣的模板可解 LC 340 (k 種) 等變體