刷题打卡记录更新到第五篇，今天聊的是“水果成篮”这道题。题面包装得很生活化：农场上有一排果树，每棵树结一种水果，你有两个篮子，每个篮子只能装同一种水果，从任意一棵树开始往右摘，遇到第三种水果就必须停下来，问最多能摘多少棵。翻译成程序员的语言就一句话：给定一个整数数组，求最长的连续子数组长度，要求子数组里最多出现两种不同的数字。这题在题库里编号是904，标的是中等难度，但滑动窗口思路掌握之后写起来其实很顺畅。

这篇文章主要面向两类人：一类是刚接触滑动窗口、想找经典题练手的C++初学者；另一类是那种看解析觉得“秒懂”，关上答案自己写就卡壳的选手。我会从题意拆解、容器选择、代码实现到调试坑位一条龙讲清楚，争取你合上手机自己也能把完整代码写出来。

1. 题目理解与整体思路拆解

1.1 把农场背景翻译成数组模型

先过一遍题意，因为“水果成篮”这个翻译有时候会让人误解连续性。题目描述是你必须从某一棵树开始，一棵一棵往右收，不能跳过果树，只要下一棵树的水果种类不属于你篮子里已有的两类，就得停。这也意味着最终答案一定是一个连续的子数组，不能中间断开重新选起点。

举个例子：fruits = [1, 2, 1, 3, 2]，正确答案是3。为什么？你可以从第0棵开始，依次摘到1、2、1，这三点连续且只出现两种水果1和2；继续往右遇到3，种类变成三种，已经超出篮子容量，只能停。如果你从第1棵开始，最多摘2、1，长度2；从第3棵开始摘3、2，长度也只有2。所以答案是3。

这里最关键的两个约束：一是“连续”，二是“最多两种”。很多新手看完题会以为和“子序列”有关，就去想排列组合，方向就歪了。只要把题面翻译成“最长连续子数组 + 最多两种不同数字”，这题就已经解决一半了。

1.2 为什么这题一定用滑动窗口

暴力做法很容易想到：枚举所有起点i和终点j，再统计fruits[i..j]里有多少种数字，O(n^2)甚至O(n^3)，数组长度一上10^5就彻底跑不动。

滑动窗口之所以适用，是因为这个问题的窗口状态有单调性：右指针每加入一个新元素，窗口内的水果种类数只会不变或者加一，不可能减少；左指针每移走一个元素，种类数只会不变或者减一，不可能增加。也就是说，扩张让窗口“变坏”，收缩让窗口“变好”，整个过程可以用两个指针来回推着维护。

可以把它想象成一把可伸缩的尺子：右端一直往前试探，一旦发现窗口里的种类超过2，就把左端往回收，直到窗口重新合法。每移动一步，计数只需要做增量修改，不需要重新扫描整个窗口。这就是滑动窗口能拿到O(n)复杂度的根本原因。

顺便说一句，不要死记“最长用右扩左收，最短用右扩收左伸”这种口诀。核心是先定义好“合法窗口”是什么，再想清楚右指针和左指针分别让合法状态怎么变化。水果成篮的合法性就是distinct <= 2，这个定义清晰了，代码就是水到渠成的事。

1.3 复杂度预估与C++容器适配

时间上，每个元素最多被右指针碰一次、被左指针碰一次，所以总操作次数是线性的，O(n)。空间上，不管数组多长，窗口内同时最多只有两种水果，算哈希表的话最多存3个键，所以是O(1)。

C++里最常见的选择是unordered_map<int, int>，用来记录每个水果类型在当前窗口里出现了几次。为什么不用map？因为这里只需要按下标查找、修改、删除，不需要按键的顺序遍历，哈希表平均O(1)显然更合适。为什么不用set？因为set只能判断“有没有”，没法判断“还有几个”，而左指针收缩时恰恰需要知道某一种水果是不是已经完全被移出窗口。

2. 核心细节解析与实操要点

2.1 为什么记录频次而不是只记录类型集合

这是这题最容易理解错的一步。假设当前窗口是[1, 2, 1]，三种水果还没超，因为去重后只有{1, 2}。右指针再读入一个3，窗口变成[1, 2, 1, 3]，此时去重集合是{1, 2, 3}，超了。

要恢复合法窗口，我们需要把左指针往右移。但关键来了：如果左指针移出的是1，窗口变成[2, 1, 3]，类型仍然是{2, 1, 3}，还是不合法。所以光知道集合里有哪些类型不够，还得知道每种类型在窗口里还剩下几次。计数为0才能认为这个类型真正离开了窗口。

所以容器里存的是次数，不是存在性。这一点想通了，下面收缩逻辑才不会写歪。

2.2 收缩时用while而不是if

窗口出现第三种水果以后，必须一直收缩到合法状态，所以是while (freq.size() > 2)，不是if。很多人写if是因为看过“无重复字符的最长子串”那题，那边左指针动一次窗口就合法了，因为重复字符移走一个就不重复。但水果成篮不一样，你移动一次左指针，可能移走的某种水果在窗口其他地方还有剩余，种类数根本没变化，必须继续移。

举例：窗口是[1, 2, 1, 3]，用if移掉第一个1，还剩[2, 1, 3]，三种水果依然在。只有持续移动，直到某一种水果次数减到0，窗口才能真正回到两种以内。所以这里不能用if糊弄。

有些老哥会说“我写if提交也过了”，这多半是测试数据没打到那个边界，逻辑上的正确性是站不住的。刷题平台最喜欢用隐藏极端数据卡这种“碰巧过”的写法。

2.3 计数减到0必须erase

freq.size()是判断窗口类型数量的唯一依据，所以当某种水果次数减到0时，一定记得从哈希表里删掉这个键。如果不删，freq.size()会一直保留历史类型数，永远不能准确反映当前窗口。

比如窗口从[1,1,2,3]收缩到[2,3]，如果1的次数减到0不erase，哈希表里还有{1:0,2:1,3:1}，size是3，但实际窗口只有两种。此时哪怕再插入一个2，程序会以为还在“非法状态”继续乱缩，最后答案偏小。

提示：调试时可以打印一下freq的size，如果它只会变大不会变小，十有八九是忘了erase。

2.4 更新答案的位置：先收缩再更新

每次右指针读完一个元素，当前窗口可能合法，也可能不合法。但不合法窗口的长度不能作为答案候选，所以必须等while收缩结束、窗口重新合法后，再执行ans = max(ans, right - left + 1)。

如果把更新写在收缩之前，等于把一个“包含三种水果的非法窗口”拿来和答案比较，逻辑上就错了。有些情况下答案碰巧没变，但一旦数据设计得刁钻，正确性就没法保证。先收缩、后更新这个顺序，就当做一个固定习惯去写。

3. 实操过程：C++代码实现与逐步优化

3.1 第一版：标准滑动窗口，先保证正确

先给出最容易理解、也最容易写对的版本。用unordered_map<int, int>记录窗口内每种水果出现次数。

#include <vector> #include <unordered_map> #include <algorithm> using namespace std; int totalFruit(vector<int>& fruits) { unordered_map<int, int> freq; int left = 0; int ans = 0; int n = fruits.size(); for (int right = 0; right < n; ++right) { freq[fruits[right]]++; while (freq.size() > 2) { int type = fruits[left]; freq[type]--; if (freq[type] == 0) { freq.erase(type); } ++left; } ans = max(ans, right - left + 1); } return ans; }

这个版本的逻辑相当直接：右指针负责扩张，把新水果塞进哈希表；while负责收缩，左指针清理多余的水果；每次收缩完用窗口长度更新答案。

我自己刷题时喜欢先写这个版本，因为不容易出错。尤其erase那步，写上去之后freq.size()的语义就非常干净，调试时看状态一眼就知道当前窗口有几种。

3.2 第二版：用数组替代哈希表，性能更好

很多平台的水果编号范围是固定的，比如0 <= fruits[i] <= 100000。既然值域已知且不大，就可以用定长数组当计数器，配合一个distinct变量记录当前窗口类型数。这种写法避开了哈希表的动态扩容和取模运算，实际跑起来通常更快。

#include <vector> #include <algorithm> using namespace std; int totalFruit(vector<int>& fruits) { vector<int> freq(100001, 0); int left = 0; int distinct = 0; int ans = 0; int n = fruits.size(); for (int right = 0; right < n; ++right) { if (freq[fruits[right]] == 0) { ++distinct; } ++freq[fruits[right]]; while (distinct > 2) { int type = fruits[left]; --freq[type]; if (freq[type] == 0) { --distinct; } ++left; } ans = max(ans, right - left + 1); } return ans; }

数组版本的关键区别是用distinct变量替代了freq.size()。因为数组没法像哈希表那样删掉某个键，只能通过计数是否为0来维护“当前窗口里到底有几种”。distinct初始为0，每次加入一个原本不在窗口的类型就加一，每次某种类型计数降到0就减一。

这个版本有两个前置条件：值域已知、范围不能太大。如果题目里水果编号可能上到1e9，或者根本没有给范围，就不要硬开数组。不同情况下选型可以这样判断：

对于比赛和笔试来说，一般优先写哈希表版本，思路清晰、不容易翻车。如果确认平台数据范围友好，再改成数组优化。

3.3 进阶：状态机写法，空间O(1)但容易踩坑

网上还有种不借助哈希表的写法：只用两个变量记录当前窗口里的两种水果类型，再用一个last数组记录每种类型最后一次出现的位置。当新类型出现时，把“最后出现位置更靠左”的旧类型整个淘汰，左指针直接跳到那个位置的下一个位置。

#include <vector> #include <algorithm> using namespace std; int totalFruit(vector<int>& fruits) { int n = fruits.size(); if (n <= 2) return n; int a = fruits[0]; int b = -1; int left = 0; vector<int> last(100001, -1); last[a] = 0; int ans = 0; for (int right = 0; right < n; ++right) { int x = fruits[right]; last[x] = right; if (b == -1 && x != a) { b = x; } else if (x != a && x != b) { if (last[a] < last[b]) { left = last[a] + 1; a = x; } else { left = last[b] + 1; b = x; } } ans = max(ans, right - left + 1); } return ans; }

这段代码看着很短，但我不建议新手第一版就写。它把“窗口收缩”这个动作隐藏在类型替换里，稍不留神就会把left跳错位置。我自己当时手推了好几个例子，比如[1,2,1,3,2]和[1,2,3,2,1]，确认替换逻辑没写反，才敢拿来用。

如果是真实面试或者笔试，优先保证正确性和可读性，老老实实写滑动窗口+哈希表版本就够。状态机写法适合已经对滑动窗口非常熟练、想挑战一下极简解的人去研究。

3.4 手动跑一遍完整过程

拿[1, 2, 1, 3, 2]为例，用第一版代码模拟一次，便于你建立画面感：

看到right=3那行：读入3之后窗口里有三种水果，先移掉位置0的1，还剩{1,2,3}三种；再移掉位置1的2，1的计数归零，erase掉，窗口变成{1,3}，左指针停在2。这就是while持续收缩的结果。

4. 常见问题与排查技巧实录

4.1 边界问题：空数组和单元素数组

空数组返回0，单元素数组理论上也能跑出1。但如果代码里ans初始化为0就没问题，for循环只执行一次或零次，逻辑自然正确。怕的是有人图省事把ans初始化为1，空数组时直接返回错误答案。统一建议ans = 0，兼容各种边界。

4.2 忘记处理计数到0的键，size膨胀

这是我见过最多的低级错误。错误写法是：

freq[fruits[left]]--; ++left;

少了if (freq[...] == 0) freq.erase(...)这一步。后果很直接：freq.size()永远是只增不减。外层while判断一直认为窗口非法，左指针会一路扫到数组末尾，最后答案被收缩成0或者一个极小值。

排查技巧：在循环里打印freq.size()，如果它从来不变小，优先检查是否漏了erase，或者distinct变量是否漏了减一。

4.3 把while写成if，逻辑不严谨

if只收缩一次，不能保证窗口恢复合法，前面已经分析过。用if能不能跑对一部分测试用例？可能可以，但那些用例多半没有让“移走一次还有剩余”的情况恰好破坏答案。写算法题不能靠运气，正确性必须能被严格论证。只要记住“收缩到合法状态”这一条，就不会再犯。

4.4 数组开错大小导致越界

有的朋友看到数组优化版本，直接写成vector<int> freq(fruits.size(), 0)，然后拿fruits[i]当下标访问。一旦fruits[i]的数值大于等于数组长度，就会越界。水果编号和水果个数没有必然关系，编号范围是0到100000，所以要么用unordered_map，要么开100001大小的数组。这个坑平时不容易出现，数据一旦不友好，程序直接崩或者出现随机值。

4.5 问题速查表

把上面这些坑整理成一张表，方便以后快速定位：

5. 一点延伸体会

水果成篮这题我觉得很适合当成滑动窗口系列的第二讲来刷。第一讲通常是“无重复字符的最长子串”，那边的窗口合法性是“窗口内没有重复字符”，收缩逻辑往往一次移动就够；到水果成篮就变成“窗口内不超过两种类型”，同样的问题换个约束条件，对while收缩的理解就更深刻了。把这两题放在一起对比着学，比孤立刷十道题还有用。

再往深处说，这题把2改成一个更大的K，解法几乎不用变，只把while (distinct > 2)改成while (distinct > K)，就是“最多包含K种不同整数的最长子数组”经典变种。所以吃透一题，等于把一类题都串起来了。

我在实际操作中还有一个习惯：每次刷完这题，会把AC代码旁边补一句“这题核心门槛在于为什么必须while收缩”，而不只是记一个答案。毕竟刷题打卡的意义不是让提交列表多一次绿色，而是下次遇到类似题目时能更早意识到“窗口合法性的维持方式”这个关键点。