LeetCode 904：水果成篮（滑动窗口） —— 题解

👋 欢迎阅读

一.题目

904. 水果成篮 - 力扣（LeetCode）

​

🎯 欢迎来到「水果成篮」题解之旅！本文将带你从“用两个篮子采摘最多水果”这一趣味场景出发，深入理解滑动窗口（双指针）的灵活运用，并掌握如何通过维护窗口内水果种类不超过 2 种来高效求解最长连续子数组长度。

在开始之前，建议你先：

• 了解题目背景：这是 LeetCode 904 题，给定一个整数数组fruits，每个数字代表一种水果类型。你只能从某棵树开始，连续向右采摘，且全程只能使用两个篮子（即最多包含两种不同的水果），一旦遇到第三种水果就必须停止。目标是求最多能采摘的果树数量。本质上，我们要找最长的连续子数组，使得其中不同元素的个数 ≤ 2。

• 明确学习目标：掌握滑动窗口核心流程——右指针不断扩展，将新水果加入窗口并统计其出现次数；若窗口内水果种类超过 2，则移动左指针缩小窗口，直至种类数恢复为 2；在每次调整后更新窗口长度的最大值。理解如何用哈希表（数组模拟）和种类计数器来高效判断窗口是否合法，并熟练实现“入窗口 → 判断 → 收缩 → 更新”的标准模板。

• 准备好环境：建议在本地 IDE 或 LeetCode 在线编辑器中打开代码，边看边运行，亲手验证示例（如fruits = [0,1,2,2]输出3，fruits = [1,2,3,2,2]输出4）。

本文将从问题转化、滑动窗口策略设计（种类计数约束）、窗口收缩条件到代码实现，层层递进。即使你对滑动窗口还不熟悉，我们也会从“维护一个最多包含两种水果的窗口，并尽量拉长它”这一直觉出发，让你轻松抓住核心思想——窗口内水果种类是唯一限制条件，用双指针动态调整窗口，在满足条件时记录最大长度。现在，让我们一起在果林中滑动窗口，摘取最多的果实吧！ 🍎🍌

二.做题思路

一、问题分析（前置分析）

给定一个整数数组fruits，每个元素代表一棵树上的水果类型。你只有两个篮子，每个篮子只能装一种类型的水果，但数量不限。你必须从某棵树开始，连续采摘，直到遇到第三种水果类型为止。目标是收集尽可能多的水果（即最长连续子数组，其中最多包含两种不同的水果类型）。
核心观察：等价于寻找一个最长的连续子数组，其中不同元素的种类数 ≤ 2。这正好适合滑动窗口来解决。

二、算法策略（滑动窗口 + 哈希计数）

• 使用数组nums[100001]（或哈希表）记录当前窗口内每种水果出现的次数。

• 使用变量basket记录当前窗口内不同水果的种类数。

• 右指针right从 0 到 n-1 依次遍历：

  • 入窗口：nums[fruits[right]]++；若该水果之前次数为 0（即新类型），则basket++。

  • 判断条件：若basket > 2，则需收缩左指针left，直到窗口内种类数 ≤ 2。

  • 收缩时，将fruits[left]移出窗口，若其计数变为 0，则basket--，left++。

  • 更新结果：每次调整后，计算当前窗口长度right - left + 1，并更新最大值len。

示例执行过程（fruits = [1, 2, 3, 2, 2]）：

最终len = 4，对应子数组[2, 3, 2, 2]，与示例一致。

三、正确性说明（简单版本）

滑动窗口始终维护最多包含两种水果类型的连续子数组。当窗口内种类数超过 2 时，必须移动左指针直到种类数 ≤ 2，因为继续扩展右指针不会减少种类数。这种“不满足就收缩”的策略，保证了在右指针固定的情况下，当前窗口是以该右端点为结尾的最长有效子数组。遍历所有右端点，记录最大值，即可得到全局最优解。由于每个元素最多入窗出窗一次，算法正确且高效。

四、实现细节（边界防护）

• 使用int nums[100001] = {0}统计水果出现次数（根据题目提示，水果类型 ≤ 100000）。

• 变量basket记录当前窗口内不同水果的种类数。

• for (int right = 0; right < n; ++right)遍历：

  • 入窗口：nums[fruits[right]]++；若该类型首次出现（nums[fruits[right]] == 1），则basket++。

  • 若basket > 2：while (left < right && basket > 2)循环收缩：

    • nums[fruits[left]]--；若变为 0，则basket--；left++。

  • 更新len = max(len, right - left + 1)。

• 时间复杂度 O(n)，空间复杂度 O(100001)（常数空间）。

五、返回值（目标映射）

返回len，即能收集到的最大水果数量。

三.代码

#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution { public: int totalFruit(vector<int>& fruits) { // 算法思路：滑动窗口（双指针） // 题目本质是求最长连续子数组，使得子数组中不同元素的种类数不超过2。 // 使用哈希表（数组模拟）记录窗口内每种水果的出现次数，用 basket 记录窗口内不同水果的种类数。 // 右指针不断扩展，增加水果计数；如果新增水果是第一次出现，则 basket 增加。 // 如果 basket > 2，则左指针右移，移出水果，如果该水果计数变为0，则 basket 减少。 // 在满足条件时更新窗口最大长度。 // 注意：这里局部数组命名为 count 以避免与参数 fruits 重名（原代码使用 nums 会导致隐藏参数，编译警告/错误） int count[100001] = {0}; // 哈希表，记录每种水果在窗口内的出现次数（水果类型范围假设为 0~100000） int basket = 0; // 当前窗口中不同水果的种类数 int n = fruits.size(); int len = 0; // 记录满足条件的最长窗口长度 // 双指针 left 和 right 定义窗口 [left, right] for (int left = 0, right = 0; right < n; right++) { // 入窗口：将 fruits[right] 加入窗口，增加其计数 count[fruits[right]]++; // 如果加入后该水果是第一次出现（计数变为1），则不同水果种类数加1 if (count[fruits[right]] == 1) { basket++; } // 判断条件：如果窗口内不同水果种类超过2，则需要收缩左边界 while (left < right && basket > 2) { // 出窗口：将 fruits[left] 移出窗口，减少其计数 count[fruits[left]]--; // 如果移出后该水果计数变为0，则不同水果种类数减1 if (count[fruits[left]] == 0) { basket--; } left++; // 左指针右移，缩小窗口 } // 更新结果：当前窗口满足条件（不同水果种类 <= 2），计算窗口长度 len = max(len, right - left + 1); } // 返回最长连续子数组的长度（即可采摘的最大水果数量） return len; } }; int main() { // 测试用例：水果序列 [1,2,1]，最多两种不同水果，整个数组都可以采摘，长度为 3 vector<int> fruits = {1, 2, 1}; Solution sol; int result = sol.totalFruit(fruits); cout << result << endl; // 输出 3 return 0; }

四、易错点分析

难点一：basket与哈希表计数的联动关系

cpp

count[fruits[right]]++; if (count[fruits[right]] == 1) { basket++; }

为什么容易混淆？
basket记录的是窗口中不同水果的种类数，而count记录的是每种水果出现的次数。当右指针扩展时，只有该水果第一次出现（计数从 0 变 1）时，basket才增加；如果该水果之前已经在窗口中，则basket不变。
这里的难点在于理解“新增元素不一定增加种类数”，需要同时关注计数变化和种类变化的区别，否则容易错误地认为每次入窗口basket都加 1。

难点二：收缩窗口时，left的移动与basket减少的条件

while (left < right && basket > 2) { count[fruits[left]]--; if (count[fruits[left]] == 0) { basket--; } left++; }

核心难点：
左指针右移时，只有当移出的水果计数变为 0（即该种类在窗口中完全消失）时，basket才减 1；否则种类数不变。
这要求理解“种类数”是独立于数量的概念，即使某个水果还有剩余，种类数也不会减少。初学者可能误以为每移出一个元素都要basket--，导致计数错误。

难点三：while循环条件left < right的必要性

while (left < right && basket > 2)

为什么需要left < right？
当窗口长度为 1 时，left == right，此时若basket > 2不可能成立（因为只有一个元素），但为了安全防止left超过right，加入left < right作为保护条件。
难点在于：即使不加这个条件，本算法在left越过right后也能结束（因为basket会降为 0 或 1），但加上后逻辑更清晰，理解上需要区分“收缩窗口”和“窗口空”的边界情况。

难点四：更新长度的时机与位置

len = max(len, right - left + 1);

难点在于为什么放在while之后？
因为经过while收缩后，窗口一定满足basket ≤ 2，此时窗口是合法的，所以可以用当前right和left计算长度。
如果放在while之前，可能窗口非法（basket > 2）时也更新长度，导致错误。理解“先处理非法状态，再记录合法状态”的顺序是掌握本算法的关键。

五、流程图

🎯 闭幕

🎉 恭喜你完成了「水果成篮」问题的学习！

为了巩固知识并进一步拓展，建议你：

🚀动手实践
在 LeetCode 上提交代码，尝试不同的测试用例。

💡深入思考

• 本题本质是求最长连续子数组，使得子数组中不同元素的种类数不超过 2。代码中使用basket记录窗口内不同水果的种类数，count数组记录每种水果的出现次数。请问为什么当新加入的水果第一次出现时（count == 1），就增加basket，而移出水果时若count == 0就减少basket？这种计数方式的依据是什么？

• 滑动窗口在basket > 2时收缩左指针，每次只移动一步并更新计数。如果窗口内包含多种水果且某些水果计数很大，为什么一次只移动一步仍能保证 O(n) 复杂度且不会遗漏最优解？

📚延伸挑战

• 如果问题改为最多可以采摘 k 种不同的水果（即篮子数量为 k，而不是固定 2 种），代码应如何通用化？

• 如果要求采摘的水果种类必须恰好为 2 种（而非不超过 2 种），滑动窗口的条件应如何修改？

如果你觉得本文对你有所帮助，欢迎：

👍点赞 / 收藏
👤关注作者，获取更多题解
💬留言交流你的疑问或优化思路

📌深入思考答案

• 计数方式依据：basket表示当前窗口内有效不同值的个数，当某个水果从 0 变为 1 时，说明窗口新增了一个种类，因此basket++；当某个水果计数从 1 变为 0 时，说明该种类在窗口中已消失，basket--。这种“进出”计数完全反映了窗口内实际存在的不同种类数。

• 一次移动一步是滑动窗口的标准操作，因为右指针每次只扩展一个元素，左指针也至多移动一步就能使窗口重新合法，且每个位置作为窗口左端点只会被移出一次，总移动次数 O(n)，不会遗漏任何长度更短的合法窗口，因为所有可能的右端点都被遍历过。

🔍延伸挑战答案

• 挑战1：将硬编码的2改为参数k，basket > k时收缩窗口，即可支持任意篮子数量，代码其他逻辑不变。

• 挑战2：若要求恰好 2 种，则需同时满足basket == 2才更新答案，窗口内不能少于 2 种。但若整个数组只有一种水果，则无法满足，此时应返回 0；需额外处理：只有在basket == 2时才更新长度，否则不更新（或单独记录单种的情况）。

祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨