刷题打卡记录更新到第五篇今天聊的是“水果成篮”这道题。题面包装得很生活化农场上有一排果树每棵树结一种水果你有两个篮子每个篮子只能装同一种水果从任意一棵树开始往右摘遇到第三种水果就必须停下来问最多能摘多少棵。翻译成程序员的语言就一句话给定一个整数数组求最长的连续子数组长度要求子数组里最多出现两种不同的数字。这题在题库里编号是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_mapint, 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必须erasefreq.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_mapint, int记录窗口内每种水果出现次数。#include vector #include unordered_map #include algorithm using namespace std; int totalFruit(vectorint fruits) { unordered_mapint, 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(vectorint fruits) { vectorint 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或者根本没有给范围就不要硬开数组。不同情况下选型可以这样判断方案适用场景优点缺点unordered_map值域未知或稀疏通用不依赖数据范围哈希开销略大定长数组值域已知且集中速度快缓存友好范围大时浪费内存甚至不可行对于比赛和笔试来说一般优先写哈希表版本思路清晰、不容易翻车。如果确认平台数据范围友好再改成数组优化。3.3 进阶状态机写法空间O(1)但容易踩坑网上还有种不借助哈希表的写法只用两个变量记录当前窗口里的两种水果类型再用一个last数组记录每种类型最后一次出现的位置。当新类型出现时把“最后出现位置更靠左”的旧类型整个淘汰左指针直接跳到那个位置的下一个位置。#include vector #include algorithm using namespace std; int totalFruit(vectorint fruits) { int n fruits.size(); if (n 2) return n; int a fruits[0]; int b -1; int left 0; vectorint 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读入收缩前freq收缩后freqleft窗口长度ans01{1:1}{1:1}01112{1:1,2:1}{1:1,2:1}02221{1:2,2:1}{1:2,2:1}03333{1:2,2:1,3:1}{1:1,3:1}22342{1:1,3:1,2:1}{2:1,3:1}323看到right3那行读入3之后窗口里有三种水果先移掉位置0的1还剩{1,2,3}三种再移掉位置1的21的计数归零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 数组开错大小导致越界有的朋友看到数组优化版本直接写成vectorint freq(fruits.size(), 0)然后拿fruits[i]当下标访问。一旦fruits[i]的数值大于等于数组长度就会越界。水果编号和水果个数没有必然关系编号范围是0到100000所以要么用unordered_map要么开100001大小的数组。这个坑平时不容易出现数据一旦不友好程序直接崩或者出现随机值。4.5 问题速查表把上面这些坑整理成一张表方便以后快速定位症状可能原因修复方案结果一直偏小计数到0没有erase或distinct没减减到0时删除键/减distinct结果偏大用非法窗口更新答案先收缩再更新用while不用if死循环while收缩时忘写left每次循环让左指针前进数组越界vector大小按数组长度开而不是按值域开使用unordered_map或固定值域数组空数组返回非0ans初始化成1初始化ans05. 一点延伸体会水果成篮这题我觉得很适合当成滑动窗口系列的第二讲来刷。第一讲通常是“无重复字符的最长子串”那边的窗口合法性是“窗口内没有重复字符”收缩逻辑往往一次移动就够到水果成篮就变成“窗口内不超过两种类型”同样的问题换个约束条件对while收缩的理解就更深刻了。把这两题放在一起对比着学比孤立刷十道题还有用。再往深处说这题把2改成一个更大的K解法几乎不用变只把while (distinct 2)改成while (distinct K)就是“最多包含K种不同整数的最长子数组”经典变种。所以吃透一题等于把一类题都串起来了。我在实际操作中还有一个习惯每次刷完这题会把AC代码旁边补一句“这题核心门槛在于为什么必须while收缩”而不只是记一个答案。毕竟刷题打卡的意义不是让提交列表多一次绿色而是下次遇到类似题目时能更早意识到“窗口合法性的维持方式”这个关键点。 
长河君 · 2026/10/16 10:42:19 · 阅读 1.2k 滑动窗口经典题：水果成篮（LeetCode 904）C++解法解析
刷题打卡记录更新到第五篇今天聊的是“水果成篮”这道题。题面包装得很生活化农场上有一排果树每棵树结一种水果你有两个篮子每个篮子只能装同一种水果从任意一棵树开始往右摘遇到第三种水果就必须停下来问最多能摘多少棵。翻译成程序员的语言就一句话给定一个整数数组求最长的连续子数组长度要求子数组里最多出现两种不同的数字。这题在题库里编号是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_mapint, 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必须erasefreq.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_mapint, int记录窗口内每种水果出现次数。#include vector #include unordered_map #include algorithm using namespace std; int totalFruit(vectorint fruits) { unordered_mapint, 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(vectorint fruits) { vectorint 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或者根本没有给范围就不要硬开数组。不同情况下选型可以这样判断方案适用场景优点缺点unordered_map值域未知或稀疏通用不依赖数据范围哈希开销略大定长数组值域已知且集中速度快缓存友好范围大时浪费内存甚至不可行对于比赛和笔试来说一般优先写哈希表版本思路清晰、不容易翻车。如果确认平台数据范围友好再改成数组优化。3.3 进阶状态机写法空间O(1)但容易踩坑网上还有种不借助哈希表的写法只用两个变量记录当前窗口里的两种水果类型再用一个last数组记录每种类型最后一次出现的位置。当新类型出现时把“最后出现位置更靠左”的旧类型整个淘汰左指针直接跳到那个位置的下一个位置。#include vector #include algorithm using namespace std; int totalFruit(vectorint fruits) { int n fruits.size(); if (n 2) return n; int a fruits[0]; int b -1; int left 0; vectorint 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读入收缩前freq收缩后freqleft窗口长度ans01{1:1}{1:1}01112{1:1,2:1}{1:1,2:1}02221{1:2,2:1}{1:2,2:1}03333{1:2,2:1,3:1}{1:1,3:1}22342{1:1,3:1,2:1}{2:1,3:1}323看到right3那行读入3之后窗口里有三种水果先移掉位置0的1还剩{1,2,3}三种再移掉位置1的21的计数归零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 数组开错大小导致越界有的朋友看到数组优化版本直接写成vectorint freq(fruits.size(), 0)然后拿fruits[i]当下标访问。一旦fruits[i]的数值大于等于数组长度就会越界。水果编号和水果个数没有必然关系编号范围是0到100000所以要么用unordered_map要么开100001大小的数组。这个坑平时不容易出现数据一旦不友好程序直接崩或者出现随机值。4.5 问题速查表把上面这些坑整理成一张表方便以后快速定位症状可能原因修复方案结果一直偏小计数到0没有erase或distinct没减减到0时删除键/减distinct结果偏大用非法窗口更新答案先收缩再更新用while不用if死循环while收缩时忘写left每次循环让左指针前进数组越界vector大小按数组长度开而不是按值域开使用unordered_map或固定值域数组空数组返回非0ans初始化成1初始化ans05. 一点延伸体会水果成篮这题我觉得很适合当成滑动窗口系列的第二讲来刷。第一讲通常是“无重复字符的最长子串”那边的窗口合法性是“窗口内没有重复字符”收缩逻辑往往一次移动就够到水果成篮就变成“窗口内不超过两种类型”同样的问题换个约束条件对while收缩的理解就更深刻了。把这两题放在一起对比着学比孤立刷十道题还有用。再往深处说这题把2改成一个更大的K解法几乎不用变只把while (distinct 2)改成while (distinct K)就是“最多包含K种不同整数的最长子数组”经典变种。所以吃透一题等于把一类题都串起来了。我在实际操作中还有一个习惯每次刷完这题会把AC代码旁边补一句“这题核心门槛在于为什么必须while收缩”而不只是记一个答案。毕竟刷题打卡的意义不是让提交列表多一次绿色而是下次遇到类似题目时能更早意识到“窗口合法性的维持方式”这个关键点。