第5天刷题打卡，我挑了“水果成篮”这道题。说实话，刚看到题目名字的时候，我以为是道模拟题，想着果树和篮子的场景，怎么也得写个状态机之类的东西。结果认真读完才发现，它其实是典型的滑动窗口题，用一个窗口加一个哈希表就能解决。这篇记录里，我会把题目理解、暴力版本、滑动窗口版本、C++ 实现细节以及我在调试过程中踩过的坑都梳理一遍，希望能帮到正在刷双指针题型的朋友。
1. 先拆题：水果成篮到底在求什么
这道题第一次看题目描述的时候，我真没意识到它是个滑动窗口题，还以为是模拟或者贪心。场景大概是这样的：一位果农有一排果树，每棵树上结的是一种水果，不同数字代表不同水果种类。现在手里有两个篮子，每个篮子只能装一种水果。从任意一棵树开始往右采，每次只能采当前这棵树的全部水果放进篮子里，一旦遇到第三种水果，篮子装不下，就必须停下来。问最多能采多少个水果。
把这段话翻译成程序员能听懂的语言，其实就是：给定一个整数数组，求一个最长的连续子数组，使得这个子数组中最多只包含两种不同的值。没错，这就是“水果成篮”的题面核心。看起来绕了个果园的弯子，本质上还是数组加区间的问题。
我最初看到这个题目时的第一反应是“用一个集合记录碰到过的水果种类，边走边统计，种类一旦超过2就停”，但其实这个想法有一个漏洞：因为起点是可以任意选的，不同的起点可能得到不同的结果。如果题目允许只从一个固定起点出发，那很简单，直接遍历一次就能结束；但“任意起点”这个条件意味着要枚举每个起点来找最大值，这才是计算量的来源。题目给出的数据范围又偏偏很大，如果真去枚举所有起点，最坏情况下就是平方级别的复杂度，直接超时。
所以这道题其实是在考察两件事：第一，你能不能从花里胡哨的描述里提炼出“最多含两种不同数字的最长连续子数组”这个模型；第二，你能不能想到用滑动窗口把平方复杂度降到线性。这两个能力在笔试题里非常常见，尤其是滑动窗口，几乎可以说是双指针体系里最容易考到的题型之一。
我这次做题的时候，遵循的路径其实比较典型：先把暴力版本写出来，跑通小样例；然后看数据范围，意识到暴力必挂；接着尝试优化，最后才落到滑动窗口。整个过程花了不少时间，但收获也明显比直接看题解多。下面把我的思路和实现细节都拆开来讲。
2. 从暴力到滑动窗口：我的思路演进过程
2.1 暴力法：最直观也最容易超时
第一版我是这么想的：外层循环枚举起点，内层循环从起点往右走，用一个哈希集合记录当前已经出现过的水果种类。每遇到一种新水果，先判断集合里有没有，如果集合大小已经等于2而且又是新种类，就停下；如果还能装下，就把新水果加进去，然后更新答案。
这个解法逻辑没有任何问题，小数据完全能跑对。比如数组是[1, 2, 1, 3, 2]，从下标0开始最多能采到[1, 2, 1]，答案是3；从下标1开始遇到3就是第三种水果，所以只能采[2, 1]，答案是2。暴力枚举能把这些情况都算清楚。但是，一旦数据范围上升到十万级别，外层起点有十万个，内层最坏要走到十万，乘积就是一亿到十亿次操作，哪怕每层循环体非常轻量，提交之后也会在大用例上直接超时。
我在本地测了一组长度为1万的随机数组，跑了几百毫秒，当时觉得还好，但换成10万之后，速度慢到无法接受。这也是刷题时很重要的一个习惯：不要只看逻辑是否成立，一定要盯着数据范围判断复杂度是否可行。暴力版本跑小样例能帮我们验证思路，但显然不是这道题的正解。
2.2 关键观察：为什么可以滑起来
暴力法慢，是因为每一个起点都重新走了一遍。仔细看会发现，如果我从下标0开始，窗口是[left, right]，当这个窗口刚好满足条件时，我想求所有以left开头的合法窗口最长是多少，其实不需要把right退回去重新走。
想象一条向右移动的橡皮筋。右端点不断前进，把新水果拉进窗口；当窗口内的水果种类超过两种，也就是出现第三种水果时，就说明当前窗口非法了，必须让左端点也向前移动，把某些水果从窗口左侧排出去，直到恢复合法。这个过程里，right始终没有回头，它一路向右走到底，left也在必要时同步向右走，两个指针都只前进不后退，整个扫描过程就是线性的。
这就是滑动窗口和暴力枚举最本质的区别。暴力枚举把每个起点都当独立事件处理，而滑动窗口利用了一个连续性事实：合法的窗口一定是在某个范围内连续存在的，窗口收缩时左端点移动后，之前扫描到的信息不会作废，只需通过调整left的位置让窗口重新合法。
那么维护合法状态的信息用什么存？我一开始觉得用一个集合记录种类就够了，但很快发现不够。原因是收缩的时候需要知道：当左边界那个水果被移出窗口后，如果这种水果在窗口内已经没有剩余了，它才真正算“消失”；如果还有剩余，那么即使左端点跳过这个位置，窗口内的水果种类数其实没有变化。所以必须记录每种水果在窗口内的出现次数，不能只记录有哪些种类。
2.3 窗口维护的细节思考
明确了数据结构之后，维护过程就变得很清晰。右端点每移到一个新位置，就给对应水果的计数加1。然后进入一个循环，判断当前哈希表里的键的个数是否大于2。如果大于2，说明窗口非法，需要把左边界的水果移出窗口：先把这个水果的计数减1，如果减完之后这个水果的计数变成0，就把这个键从哈希表里删除；随后left加1。这个循环不断执行，直到哈希表里只剩不超过2个键为止。这时候窗口又是合法的，用right - left + 1更新答案。
这里有一个容易纠结的点：为什么是循环而不是单次判断。因为窗口里加入一个第三种水果后，左侧可能有好几个连续位置都需要移出，才能让窗口重新合法。比如窗口是[3, 3, 1, 1, 2]，此时加入了2，窗口变成[3, 3, 1, 1, 2]，里面有3、1、2三种水果，已经超了。左边界是3，把3移出后窗口是[3, 1, 1, 2]，里面仍有3、1、2三种，还是非法，必须继续移。只有等所有3都被移出后，窗口[1, 1, 2]才合法。所以用while而不是if是必然选择。
另外还有个类似隐患：如果左边界水果计数减到0了，却忘了从哈希表里erase，那么键数量不会减少，窗口会一直被认为非法，导致left一直收缩到最后，答案就会出错。这个问题我实际调试中踩过，后面章节会单独说。
3. C++ 实现细节：代码、数据结构与边界情况
3.1 核心代码与逐行解读
最后定稿的代码非常短，这也是滑动窗口题型的典型特征，代码量不大，但逻辑密度高。
#include <unordered_map> #include <vector> #include <algorithm> using namespace std; class Solution { public: int totalFruit(vector<int>& fruits) { unordered_map<int, int> cnt; int left = 0; int ans = 0; int n = fruits.size(); for (int right = 0; right < n; ++right) { cnt[fruits[right]]++; while (cnt.size() > 2) { int type = fruits[left]; cnt[type]--; if (cnt[type] == 0) { cnt.erase(type); } ++left; } ans = max(ans, right - left + 1); } return ans; } };逐行解释几个关键位置。
第一，cnt[fruits[right]]++：这行是扩展窗口。不管当前窗口中这种水果有多少个，数量加1。cnt里的键是水果编号，值是它在窗口内出现的次数。
第二，while (cnt.size() > 2)是整个算法的核心。只要窗口里水果种类数超过2，就进入收缩流程。收缩的对象是left指向的水果，也就是当前窗口最左侧那个位置。把它移出窗口时，对应计数减1。如果减完后计数为0，说明这种水果已经完全不在窗口里了，就要把这个键从哈希表里erase掉。最后left加1，继续判断。
第三，退出while后窗口一定合法，这时候当前以right为右端点的最长合法窗口长度就是right - left + 1。用它去更新ans。
这代码里考察的细节不少。最容易被忽略的就是erase操作。如果不删键，cnt.size()永远保持旧值，程序会一直认为窗口里有三种水果，然后left一直往后走，直到把窗口收缩得特别小，甚至直接缩成空，最终答案当然不对。
还有一个细节是更新答案的位置。一定要在收缩完成的窗口状态下去计算长度。如果放在收缩之前，算出来的是非法窗口的长度，结果偏大。如果放在收缩循环内部，每次移动left都去更新，最后答案可能偏小，因为收缩过程中已经错过了最佳状态。
3.2 为什么用 unordered_map 而不是 set
我第一次尝试维护水果种类的时候，第一反应是用set，因为题目看起来只关心“有几种水果”。但试了一下就发现不够用，究其原因是收缩时需要计数。
举个例子：窗口里目前有[1, 1, 2, 2]，left指向第一个1。如果用set，只知道窗口里有1和2两类，无法知道如果移出这个1之后，1是不是就没有了。所以当left移动时，无法判断该不该把1从集合里移除。如果一律不移除，窗口的种类数就虚高；如果一律移除，又可能误判，因为窗口里可能还有另一个1。
unordered_map<int, int>把每种水果的出现次数记下来，就能精确回答“这种水果还剩几个”这个问题。当计数减到0时才删除键。这样，cnt.size()任何时候都精确等于“窗口内出现的不同水果种类数”，判断合法性的依据才可靠。
另外，和map（红黑树）相比，unordered_map的哈希实现通常更快，均摊复杂度是 O(1)。虽然这道题场景下用map也能过，但刷题时我默认优先用unordered_map，因为map的 O(logn) 查询在大量场景下没有哈希快。当然这不是绝对的，如果后续遇到需要有序遍历键的场景，map可能是更好的选择。
3.3 边界情况与额外细节
写完之后，我专门测了几个边界情况，确保代码不是只对“正常数据”有效。
第一种边界：所有水果都是同一种。比如[1,1,1,1,1]，哈希表里始终只有1一个键，cnt.size()永远等于1，不会进入收缩循环，窗口会一直扩张到整个数组，答案就是5，符合直觉。两个篮子只需要装一种水果，当然能全采。
第二种边界：只有两种水果交替出现。比如[1,2,1,2,1,2]，窗口从0一直滑到末尾，cnt.size()一直等于2，答案就是整个数组长度，也没问题。这说明两个篮子的限制恰好被满足。
第三种边界：水果编号特别大。有的测试数据里水果类型可能达到几十万甚至上百万，如果用数组实现，要开一个非常大的计数器数组，例如vector<int> cnt(1000000)，虽然可能能过，但内存浪费明显，而且一旦编号范围和数量级未知，数组方案就有越界风险。unordered_map可以抛开编号具体范围，用稀疏存储解决。
还有一个我自己补充测试的场景：数组里前段是一种水果，中段是另一种，后段直接来第三种，比如[1,1,1,2,2,3,3,3]。这里正确结果应该是5，也就是[1,1,1,2,2]或[2,2,3,3,3]，都能采到5。用代码跑，会发现left在遇到3之后会向左收缩，直到把1全部移出窗口，此时窗口变成[2,2,3]，长度为3，之后继续右扩到[2,2,3,3,3]，长度5，答案正确。这个用例覆盖了多步收缩的场景，是检查while是否正确的好例子。
4. 踩坑实录：三个容易翻车的细节
4.1 问题一：忘了 erase 掉次数为0的键
第一次实现时，我在收缩循环里只写了cnt[type]--，没有处理键删除。结果跑一个小数据就发现答案偏大。仔细排查，问题出在哈希表里残留了计数为0的键。比如窗口里某个水果已经全部移出，但键还在哈希表里，cnt.size()仍然把这个键算进去。于是本应合法的窗口被判为非法，导致left继续疯狂向右移动，最终返回了一个不正确的窗口长度。
排查方法很简单：在关键位置打印cnt.size()和窗口两端下标。一看就发现当真实种类数为2时，哈希表里却还有3个键。修复就是把计数减到0的键erase掉。这一类 bug 很隐蔽，因为编译不会报错，小数据可能碰巧也能过，一旦数据稍微大一点就会出问题。刷题的时候最好在本地就把这种场景测掉，不要等提交之后一脸懵。
4.2 问题二：收缩窗口时的顺序搞错
另一个坑是收缩左右顺序写反了。我一开始写的代码如下：
while (cnt.size() > 2) { ++left; cnt[fruits[left]]--; // ... }先移动left，再去更新计数。这样写会导致一个问题：移动left之后，fruits[left]已经不是原来那个离开窗口的水果了，而是新的左边界位置的水果。也就是说，被减计数的不是应该移出的水果，而是还留在窗口里的水果。计数错乱后，窗口状态完全不可信。
正确的顺序是：先看当前left位置的水果是什么，把它的计数减1，检查是否要erase，最后再执行++left。这个顺序其实对应着“移除左侧第一个元素”这个动作：元素先离开，窗口边界再前进。
我还犯过另一个顺序错误：先判断if (cnt[type] == 0)再减计数。这显然更离谱，因为判断的时候还没减，永远判断不出0。编码时一定要把--放在判断之前。这种边界细节最好用注释标出来，防止下次想不起来。
4.3 问题三：更新答案的时机不对
更新ans的位置也折腾了我一会儿。第一次我是这样写的：
for (int right = 0; right < n; ++right) { cnt[fruits[right]]++; ans = max(ans, right - left + 1); while (cnt.size() > 2) { // ... ++left; } }先更新ans，再收缩。问题在于，当right刚加入第三种水果时，窗口是非法的，此时计算的right - left + 1并不是合法窗口的长度，ans会被错误地更新成偏大的值。例如[1,2,1,3]，right走到3时，窗口[1,2,1,3]长度为4，但合法长度其实只有2，把4计入ans就错了。
后来我改成在收缩循环里面更新ans，也不对，因为每收缩一次窗口长度就变小一次，最终记录的可能是收缩后的某个较小值，而不是收缩完成前能保持合法的最长窗口。正确答案是：先收缩到合法状态，再用当前的right - left + 1更新ans。这个顺序从逻辑上也非常自然：窗口先满足约束条件，再谈最优长度。
5. 同类题通用框架与打卡心得
5.1 这类题型的识别与通用模板
“水果成篮”并不是一道孤立的题。这类“最多包含 k 种不同元素的最长连续子数组”其实是一大类问题的代表，通用解法就是滑动窗口加哈希计数。把题目里的 k 当成常量，这里的 k=2，就是最经典的窗口问题。
如果遇到“无重复字符的最长子串”，其实也是同一个框架，只是限制条件从“最多两种不同数字”变成了“窗口内每个字符都不同”。这种情况下收缩时的判断条件不是种类数大于2，而是某个字符的计数大于1，一旦窗口里出现重复，就不断收缩直到没有重复。
如果遇到“替换后的最长重复子串”这类题，同样可以在滑动窗口里维护某个主要字符的出现次数，通过判断窗口长度减去最大出现次数是否超过允许的替换次数来决定是否收缩。你会发现，滑动窗口的板子基本一致，难的地方在于界定“合法窗口”的条件，以及怎么高效维护这个条件。
所以刷题的时候，把题目归类比单独背一道题重要得多。看到“连续子数组”“最多/至少”“种类数/不同数”这些词，就应该下意识想到滑动窗口。写代码时可以套用下面的模板：
// 通用框架：求最多含 k 类元素的最长连续子数组 int longestWithAtMostK(vector<int>& nums, int k) { int n = nums.size(); unordered_map<int, int> cnt; int left = 0; int ans = 0; for (int right = 0; right < n; ++right) { cnt[nums[right]]++; while ((int)cnt.size() > k) { cnt[nums[left]]--; if (cnt[nums[left]] == 0) { cnt.erase(nums[left]); } ++left; } ans = max(ans, right - left + 1); } return ans; }这个模板记熟了，遇到同类题能省很多时间。但套模板之前，一定要先把“要不要收缩”和“收缩到什么时候”这两个问题想清楚，否则模板只会帮倒忙。
5.2 复杂度分析与更优的数组写法
滑动窗口解法的时间复杂度是 O(n)，因为right指针从左到右扫了一遍，left指针虽然也会右移，但每个位置最多被移出窗口一次，整体还是线性。空间复杂度方面，哈希表里最多同时存在几个键，这里 k=2，所以空间可以近似看作 O(1)。
不过，unordered_map内部还是有一定哈希开销。如果题目给的数组长度很大，而且水果编号范围已知，比如编号不超过 100000，那就可以用数组实现，连哈希表都不用开。
int totalFruit(vector<int>& fruits) { int n = fruits.size(); vector<int> cnt(100001, 0); int left = 0; int ans = 0; int kinds = 0; for (int right = 0; right < n; ++right) { if (cnt[fruits[right]] == 0) { ++kinds; } cnt[fruits[right]]++; while (kinds > 2) { int type = fruits[left]; cnt[type]--; if (cnt[type] == 0) { --kinds; } ++left; } ans = max(ans, right - left + 1); } return ans; }这里额外用一个kinds变量记录当前出现次数大于0的数字种类数。当某个计数从0变成1时kinds++，当计数从1变成0时kinds--。于是，判断窗口是否合法就等价于判断kinds > 2，省去了对cnt.size()的依赖。数组方案在本地测试时跑得更快，写法也更清爽，缺点就是必须事先知道编号的上限，而且如果编号范围非常大，开数组就不现实。平时练习我更推荐先写unordered_map版本，因为通用性和安全性更高；各种评测环境的数据范围差异大，能用一个版本兼容尽量兼容。
5.3 做题过程中的碎片心得
这次打卡，我还有一个比较大的感触是：读题目描述时，别被业务故事带偏。水果、篮子、果农，翻译成程序语言就是一个数组、一个容量限制、一个最长区间问题。类似的还有滑动窗口最大值问题里“窗口”的概念，盛水容器问题里双指针为什么能跳过很多状态。这些题的外壳都很有迷惑性，但背后都是数据结构与算法的常见模型。
代码写完以后，我习惯做一步自测：把思路在自己的小例子上走一遍，不需要跑代码，而是手推一遍窗口变化。比如[1,2,1]：right=0，窗口[1]，合法，ans=1；right=1，窗口[1,2]，两种水果，合法，ans=2；right=2，窗口[1,2,1]，仍只有两种水果，合法，ans=3。这个过程能在提交前发现大部分逻辑错漏。尤其是左右指针的起始位置、循环退出的条件这类问题，光靠脑子想容易遗漏，动手画一条时间轴就清楚多了。
另外一个刷题习惯是：如果一个题卡住超过一定时间，我会先去查同类题目的解题思路，而不是直接看完整题解。比如这道题，我知道它是滑动窗口，就先自己从暴力优化到滑动窗口，哪怕中间写错了好几次，也比直接背答案更有收获。到了提交通过之后再回头复盘，把这些踩过的坑记下来，后续再做类似题，基本上不会再犯同样的错误。
“水果成篮”本身不难，难的是你愿不愿意先在暴力解上多花几分钟，把所有细节都摸清楚。如果一上来就急着上滑动窗口，反而容易忽略为什么窗口能收缩、为什么erase是必须的。这题做下来，我在滑动窗口这类题上的手感确实比之前提升了不少，也算是在打卡记录里值得记一笔的收获。
