欢迎阅读一.题目904. 水果成篮 - 力扣LeetCode​ 欢迎来到「水果成篮」题解之旅本文将带你从“用两个篮子采摘最多水果”这一趣味场景出发深入理解滑动窗口双指针的灵活运用并掌握如何通过维护窗口内水果种类不超过 2 种来高效求解最长连续子数组长度。在开始之前建议你先了解题目背景这是 LeetCode 904 题给定一个整数数组fruits每个数字代表一种水果类型。你只能从某棵树开始连续向右采摘且全程只能使用两个篮子即最多包含两种不同的水果一旦遇到第三种水果就必须停止。目标是求最多能采摘的果树数量。本质上我们要找最长的连续子数组使得其中不同元素的个数 ≤ 2。明确学习目标掌握滑动窗口核心流程——右指针不断扩展将新水果加入窗口并统计其出现次数若窗口内水果种类超过 2则移动左指针缩小窗口直至种类数恢复为 2在每次调整后更新窗口长度的最大值。理解如何用哈希表数组模拟和种类计数器来高效判断窗口是否合法并熟练实现“入窗口 → 判断 → 收缩 → 更新”的标准模板。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如fruits [0,1,2,2]输出3fruits [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]步骤rightfruits[right]入窗后basket是否需收缩操作当前窗口[left, right]窗口长度len更新初始--0----01011否-[0,0]112122否-[0,1]223233是左移移除fruits[0]1nums[1]变为0basket2left1[1,2]22保持4322否-[1,3]335422否-[1,4]44最终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 2while (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(vectorint 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 vectorint fruits {1, 2, 1}; Solution sol; int result sol.totalFruit(fruits); cout result endl; // 输出 3 return 0; }四、易错点分析难点一basket与哈希表计数的联动关系cppcount[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改为参数kbasket k时收缩窗口即可支持任意篮子数量代码其他逻辑不变。挑战2若要求恰好 2 种则需同时满足basket 2才更新答案窗口内不能少于 2 种。但若整个数组只有一种水果则无法满足此时应返回 0需额外处理只有在basket 2时才更新长度否则不更新或单独记录单种的情况。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨