水果成篮为什么是至多两类元素的滑动窗口？

简化版

水果成篮可以理解为：找最长连续子数组，里面最多只有 2 种不同元素。

用滑动窗口和哈希表统计窗口中每种水果的数量。

右指针扩张；如果种类数超过 2，就移动左指针并减少计数，直到窗口重新只包含 2 类以内。

详细版

题目要求从某棵树开始向右摘，且两个篮子各装一种水果，所以答案必须是连续区间，并且区间内最多有两种水果。

维护 Map：

key 是水果类型；
value 是窗口中该类型出现次数；
当 Map.size > 2 时，左指针右移并减少对应计数；
某类计数变成 0 时，从 Map 删除。

每次窗口合法时，用窗口长度更新答案。

时间复杂度 O(n)，空间复杂度 O(1)，因为最多维护 3 种左右的水果类型。

完整版教学

一、如何把题目翻译成数组问题

题目故事说的是摘水果，但算法上它就是“最长连续子数组，最多包含 2 种不同值”。“从任意树开始，只能向右走”说明必须连续；“两个篮子，每个篮子只能装一种水果”说明种类数最多为 2。把故事条件翻译成窗口约束后，题目就清晰了。

记忆钩子：两个篮子就是窗口里最多两种类型，不是最多两个水果。

二、为什么用哈希表计数

窗口移动时，需要知道当前有多少种水果，以及左端移出后某种水果是否彻底消失。只用两个变量记录类型也能做，但边界容易写乱。哈希表计数更通用，也能迁移到“最多 K 种字符”的问题。

数据结构	能力	适用性
两个变量	代码短但分支多	只适合 K=2 的特化
哈希表	统一维护种类和计数	适合 K 种不同元素

面试中用 Map 更容易讲清楚窗口状态。

三、窗口何时非法

当 countMap.size > 2 时，窗口里出现了第三种水果。此时无论当前窗口长度多长，都不满足两个篮子的限制，必须移动左指针。左指针每移出一个水果，就把对应计数减 1；如果计数归零，说明这种水果已经不在窗口中，要删除 key。

while (map.size > 2) {
  const x = fruits[left]
  map.set(x, map.get(x) - 1)
  if (map.get(x) === 0) map.delete(x)
  left++
}

这段代码恢复的就是“最多两种”这个不变量。

四、带数字推演

数组 [1,2,1,3,2,2]。

窗口 [1,2,1]：两种，长度 3
加入 3 -> [1,2,1,3]：三种，非法
左缩移出 1 -> [2,1,3]：仍三种
左缩移出 2 -> [1,3]：两种，合法
继续加入 2 -> [1,3,2]：三种，再左缩

最长合法窗口是 [1,2,1] 或 [3,2,2]，长度为 3。

五、代码模板

实现如下：

function totalFruit(fruits) {
  const map = new Map()
  let left = 0
  let ans = 0
  for (let right = 0; right < fruits.length; right++) {
    const r = fruits[right]
    map.set(r, (map.get(r) || 0) + 1)
    while (map.size > 2) {
      const l = fruits[left]
      map.set(l, map.get(l) - 1)
      if (map.get(l) === 0) map.delete(l)
      left++
    }
    ans = Math.max(ans, right - left + 1)
  }
  return ans
}

这也是“至多 K 种不同元素”的标准模板，把 2 改成 K 就能复用。

六、常见误区与追问

误区：把两个篮子理解成最多摘两个水果。 两个篮子限制的是类型数，不是总数量。
误区：窗口出现第三类后直接从第三类重新开始。 可能漏掉跨越边界的更优窗口，应该按左指针逐步收缩。
误区：计数为 0 但不删除 key。 Map.size 会错误偏大，导致窗口一直被认为非法。
追问：空间复杂度为什么可以说 O(1)？ 因为窗口中种类超过 2 就收缩，Map 大小被常数限制。
追问：如何扩展到最多 K 种字符？ 把非法条件从 size > 2 改成 size > K，其他逻辑不变。

这些点能体现你是否把故事题抽象成窗口约束。

七、加强记忆

水果成篮记成“最长连续窗口，最多两种水果”。右指针负责摘新水果，Map 记录窗口里每种水果数量；一旦出现第三种，左指针就缩到只剩两种。合法后更新最大长度。这个模板和“最长包含至多 K 个不同字符的子串”完全同源。

简化版

详细版