看到“水果成篮”这个题目很多刷题的朋友第一反应是“这不就是个滑动窗口嘛”但真上手写的时候边界条件、窗口收缩时机、计数器的维护处处都是坑。这道题在力扣上是904号属于双指针专题里非常经典的一道“窗口内最多包含两类元素”的题目和“无重复字符的最长子串”并列为滑动窗口入门必刷题。今天这篇就以它为例把双指针的解题思路、代码细节、易错点一次说透顺便聊聊双指针的另一类应用——合并有序数组帮大家把这类题串成一条线。1. 题目到底在问什么读题与核心矛盾拆解1.1 场景还原与题意转化先别急着想算法我们把题面翻译成人话。你是一片果园的采摘工面前有一排果树每棵树上结的果子都有一种类型用数组里的数字表示比如[1,2,1]表示三棵树的果子类型分别是1号、2号、1号。你手里只有两个篮子每个篮子只能装同一种类型的果子也就是说你最多同时收集两种类型的果子。你从某棵树开始摘可以一路往右摘但只要你遇到的果子类型是第三种就必须停下来。问从哪棵开始摘能摘到最多的果子换成一个纯算法的说法给定一个整数数组fruits找出一个最长的连续子数组使得这个子数组中不同数字的个数不超过2返回这个子数组的长度。这两句话等价但第一句话更容易建立直觉。举个例子fruits [3,3,3,1,2,1,1,2,3,3,4]从第一个3开始摘能摘[3,3,3,1]吗能因为只有3和1两种类型。还能往里走吗下一个是2第三种类型不能要了。那从第四个元素1开始呢可以摘[1,2,1,1,2]长度为5。我们要的就是所有可能起点里能摘到的最长长度。题目要求的答案就是无论从哪棵树开始用两个篮子能收集到的最大水果数量。注意篮子里的水果类型一旦确定中途不能换但我们可以选择在任意一棵树开始这就是“贪婪的采摘者”这个名字的由来——采摘者只顾着尽可能多摘能摘就摘遇到第三种类型就止损。很多新手在这里会误解成“找数组里出现次数最多的两种数字的总出现次数”这是不对的。因为采摘必须是连续的中间不能跳过某棵树所以本质是“连续子数组”而不是“全局统计”。我当初就被这个误解坑过写完代码跑测试用例发现结果偏大才反应过来连续性这个约束有多重要。1.2 为什么这题适合用双指针既然要找一个连续区间而且区间内的“不同元素个数”这个条件会随着区间的伸缩而变化那自然能想到用双指针维护一个动态窗口。窗口的左边界和右边界分别对应采摘的起点和当前到达的位置窗口内始终满足“不同水果类型不超过2”这个约束。右指针负责扩张尽可能多摘左指针负责在约束被破坏时收缩换一个起点。整个过程下来每个元素被右指针扫过一次、被左指针扫过一次总时间复杂度O(n)空间复杂度O(1)如果用一个固定大小的计数数组或O(k)k是水果类型数如果用哈希表。对比一下暴力解法枚举所有起点i和终点j检查子数组fruits[i..j]中不同数字个数是否不超过2复杂度O(n²)甚至O(n³)如果检查函数遍历子数组在n达到10⁵量级时直接超时。双指针滑动窗口正是针对“连续子数组 某种动态约束”这类问题的最优解模板。2. 从暴力到滑动窗口思路演进与方案选型2.1 暴力解法先写出来再谈优化我刷题的习惯是拿到一道中等难度的题先别急着套模板先把最朴素的想法写出来哪怕超时至少能验证自己对题意的理解是否正确。对于“水果成篮”暴力解法非常简单public int totalFruit(int[] fruits) { int n fruits.length; int ans 0; for (int i 0; i n; i) { for (int j i; j n; j) { // 统计 fruits[i..j] 中不同数字的个数 if (countDistinct(fruits, i, j) 2) { ans Math.max(ans, j - i 1); } } } return ans; }其中countDistinct可以用一个HashSet实现。但这样做时间复杂度是O(n³)因为两层循环加每次统计都要遍历子数组。哪怕把统计优化成在第二层循环里动态维护一个HashMap复杂度降到O(n²)对n 10⁵的数据来说依然不可接受。暴力解法的意义不在效率在于帮我们确认一个关键事实答案一定是某个连续子数组的长度。有了这个认知就能进一步想有没有办法不枚举所有起点而是用一个“会移动的窗口”去扫一遍数组。2.2 滑动窗口的可行性分析为什么滑动窗口在这道题里是对的关键在于一个性质如果fruits[i..j]是一个合法的子数组不同元素不超过2那么它的任意子数组fruits[i1..j]也一定是合法的删除元素不会让不同元素个数变多。反过来如果fruits[i..j]不合法那么fruits[i..j1]也一定不合法加入元素不会让不同元素个数变少。这个性质叫做“单调性”——窗口的合法性随着右指针右移单调变差随着左指针右移单调变好。正是这个单调性让我们可以在右指针扩张到不合法时通过不断移动左指针来重新让窗口合法而不需要回退右指针。右指针不回退整体就是线性扫描这就是滑动窗口能保证O(n)复杂度的根本原因。如果题目换成“找出一个最长的子数组其中不同元素的个数恰好等于2”那单调性就被破坏了滑动窗口模板就不太好用需要额外处理恰好等于的情况。所以在动笔之前先确认约束是否满足单调性能省掉很多debug时间。3. 核心实现代码逐行拆解与参数细节3.1 Java实现计数器数组 or 哈希表水果的类型是整数而且题目一般会说0 fruits[i] fruits.length所以可以直接用一个长度等于fruits.length的数组作为计数器每次访问都是O(1)空间也是O(n)。如果类型范围未知或很大用HashMapInteger, Integer更稳妥。两种方案本质一样下面给出用数组实现的版本public int totalFruit(int[] fruits) { int n fruits.length; int[] count new int[n]; int left 0; int ans 0; int kinds 0; // 当前窗口内有几种不同的水果 for (int right 0; right n; right) { // 1. 扩张把 fruits[right] 加入窗口 if (count[fruits[right]] 0) { kinds; } count[fruits[right]]; // 2. 收缩如果类型数超过2移动左指针 while (kinds 2) { count[fruits[left]]--; if (count[fruits[left]] 0) { kinds--; } left; } // 3. 此刻窗口 [left..right] 一定合法更新答案 ans Math.max(ans, right - left 1); } return ans; }注意几个关键变量count[]记录窗口内每种水果的剩余数量kinds记录窗口内有几种不同的水果它和count数组配合避免每次判断种类数时都遍历countleft是窗口左边界right是右边界ans记录历史最大窗口长度。当while (kinds 2)收缩时每移动一次left都要把对应水果的计数减一如果减到0说明这种水果在窗口里没了kinds减一。这个while循环可能会执行多次直到窗口重新合法为止。为什么这里用while而不是if因为只移一个左边界可能不足以消除第三种水果。举个例子fruits [1,1,1,2,3]right指向3时窗口是[1,1,1,2,3]包含3种水果需要一直把左指针移过所有1窗口变成[2,3]才重新合法。用if只移一步窗口变成[1,1,2,3]依然不合法就会出错。3.2 代码的等价写法for循环 while字典版如果你更喜欢用HashMap写逻辑完全一样只是更新方式略有不同public int totalFruit(int[] fruits) { MapInteger, Integer basket new HashMap(); int left 0; int ans 0; for (int right 0; right fruits.length; right) { basket.merge(fruits[right], 1, Integer::sum); while (basket.size() 2) { basket.merge(fruits[left], -1, Integer::sum); if (basket.get(fruits[left]) 0) { basket.remove(fruits[left]); } left; } ans Math.max(ans, right - left 1); } return ans; }两种写法性能差别不大用数组统计在整数范围可控时稍快一点点用HashMap则更通用。我建议面试时先写HashMap版本因为它能自然处理类型范围不确定的情况如果面试官要求优化空间再改成数组计数器。3.3 边界条件与极端用例这类题最容易翻车的就是边界条件。我总结了几组必测的用例建议写完代码后立刻跑一遍输入期望输出解释[1]1只有一个篮子都需要时输出1[1,2]2正好两种水果全摘[1,2,1]3两种水果交替出现窗口可以持续扩张[1,2,3]2三种水果最多只能摘前两个或后两个[3,3,3,1,2,1,1,2,3,3,4]5经典用例答案来自[1,2,1,1,2][0,1,2,2]3答案来自[1,2,2]或[0,1]注意窗口收缩的时机跑这几个用例基本能覆盖“窗口从未超两类”“窗口超两类需要收缩多次”“窗口收缩到只剩一种类型”等核心场景。我每次写完滑动窗口的题都会把这类用例粘贴到本地里做回归这比在提交后等判题反馈要快得多。4. 手推全过程从3种水果回退到2种4.1 逐步推导一次完整扫描为了更直观理解左指针的收缩过程我们用手推一遍fruits [1,2,1,3,1]。初始left 0,right 0,count[1] 1,kinds 1, 窗口[1]合法ans 1。right 1加入2count[2] 1,kinds 2, 窗口[1,2]合法ans 2。right 2加入1count[1] 2,kinds不变仍为2窗口[1,2,1]合法ans 3。right 3加入3count[3] 1,kinds 3超了。进入while移动left从0到1count[1]从2降到1不为0kinds仍为3窗口[2,1,3]还是不合法移动left从1到2count[2]从1降到0kinds降到2窗口[1,3]合法停止收缩。此时ans Math.max(3, 4 - 2 1) 3。窗口内是[1,3]虽然长度只有2但后续可能扩展到更大。right 4加入1count[1] 2,kinds不变为2窗口[1,3,1]合法ans Math.max(3, 5 - 2) 3。最终答案是3最长子数组是[1,2,1]或[1,3,1]。手动推一遍就会发现整个扫描过程中right从来没回退过这就是“双指针/滑动窗口”的核心优势。4.2 为什么right不需要回退很多第一次接触滑动窗口的人都会问左指针收缩之后右指针为什么不用回到新的左指针位置重新扫原因就是前面提到的单调性。右指针扫过的区域里如果某个窗口不合法那么把它左边界右移后一旦重新合法新的合法窗口的右边界只会比原来的右边界更靠右或相等不会在更左边出现一个更优的合法窗口。换句话说我们已经“错过”的左边界所构成的窗口长度都不会超过当前记录的最优值所以直接让右指针继续往右扫不会漏掉答案。这个思想非常重要它是滑动窗口系列所有题目的基石。理解了这一点以后遇到“最长无重复子串”“最长连续1的个数最多K个0”这类题都能一眼看穿套路。5. 常见问题与排查技巧实录5.1 典型Bug忘记把计数减到0时种类数减一这是我见过最多人犯的错。如果收缩左指针时只执行count[fruits[left]]--而没有在计数变为0的时候同步kinds--那么kinds会一直虚高导致窗口明明已经合法了程序还认为不合法窗口过度收缩答案偏小。错误版代码长这样while (kinds 2) { count[fruits[left]]--; left; // 忘了 if (count[fruits[left]] 0) kinds--; }排查方法非常简单在while循环里打印left、right、kinds和count数组一眼就能看出kinds是不是该减没减。用我上面给的手推用例[1,2,1,3,1]跑一遍right3时就会发现问题。5.2 典型Bugans更新位置不对另一个常见错误是把ans Math.max(ans, right - left 1)写在while收缩之前。这样在窗口不合法的时候也会尝试更新答案可能把不合法的窗口长度记录进去。比如窗口[1,2,3]长度是3但它并不合法正确的最优解可能是2如果不小心记录了3答案就错了。正确做法是先通过while把窗口收缩到合法状态再更新答案。窗口合法的时机就是while循环结束后因为此时kinds 2且left是满足条件的最小左边界收缩得最狠长度right - left 1是右边界固定为right时的最大合法窗口长度。5.3 实战排查技巧加日志跑用例遇到答案不对不要干瞪眼。我的习惯是在关键位置加上临时日志for (int right 0; right n; right) { // 加入 fruits[right] System.out.println(right right , 加入 fruits[right]); while (kinds 2) { System.out.println( 收缩: left left , 移除 fruits[left]); // ... } System.out.println( 窗口: [ left , right ], kinds kinds); }跑一遍小规模用例看窗口的移动轨迹是否符合预期。大多数时候问题都出在“窗口的收缩没有把kinds同步更新”或者“更新ans的位置不对”这两个点上。5.4 一个微妙的小优化外层用for还是while在滑动窗口的标准写法里外层通常用for (int right 0; right n; right)每一步右指针固定前移一步。这样写的优点是逻辑清晰right的移动次数固定为n时间复杂度好分析。也有用while (right n)配合内部right的写法效果一样但代码稍显啰嗦而且容易忘记在分支里更新right造成死循环。我建议一直用for循环写外层减少心智负担。另外一个常见优化是提前退出如果当前剩余数组长度已经不可能超过ans可以提前break。比如ans n - left就可以退出。这个优化对实际性能提升有限但在极端用例下可以省一点点时间if (ans n - left) break;不过要注意这个退出判断要放在每次更新ans之后否则可能提前退出错过更优解。6. 变体与延伸从两篮到K篮以及双指针的另一副面孔6.1 泛化版本最多K种不同水果“水果成篮”最常见的变体是把两个篮子改成K个篮子即求“最长连续子数组其中不同元素个数不超过K”。代码只需要把kinds 2改成kinds K其他完全不用变。这也是力扣340题“至多包含 K 个不同字符的最长子串”的解法。所以“水果成篮”其实就是“K2”的特殊情况。遇到这种泛化题目我建议把K作为一个参数传入函数这样不仅代码复用度高面试时还能展示你对题目的抽象能力。比如public int totalFruit(int[] fruits, int k) { // 逻辑不变把 2 换成 k }6.2 双指针的另一类应用合并有序数组如果说滑动窗口是“同向双指针”那么合并有序数组用的就是“相向或分头推进的双指针”。拿“合并两个有序数组”来说经典做法是三个指针一个指向第一个数组的有效末尾一个指向第二个数组的末尾一个指向合并后数组的末尾从后往前填。这个思路和滑动窗口的区别在于两个指针不是在维护同一个窗口而是在两个数组上各走各的比大小、填结果。比如nums1 [1,2,3,0,0,0],nums2 [2,5,6]从后往前比较大的放到nums1末尾。这个操作之所以能用双指针是因为两个数组分别有序每次比较都可以确定一个元素最终放哪不会破坏有序性。很多初学者一看到“双指针”就先想滑动窗口其实双指针的应用远不止“窗口”一种形态。理解“同向”“相向”“分类讨论”这些不同模式才是真正掌握双指针的关键。6.3 刷题路径建议如果你正在系统刷双指针我的建议顺序是同向双指针滑动窗口先刷“无重复字符的最长子串”再刷“水果成篮”然后刷“最小覆盖子串”和“字符串的排列”相向双指针先刷“两数之和 II - 输入有序数组”再刷“三数之和”“盛最多水的容器”分头推进双指针刷“合并两个有序数组”“合并两个有序链表”“寻找两个正序数组的中位数”。这样按“模式”刷题比按题目难度刷更高效因为同一个模式的题核心套路是通用的每刷一道都在加深对这类题的理解。7. 写在最后的几点实在体会说实话“水果成篮”这道题本身的难度并不高但它是一道特别好的“滑动窗口教学题”。因为它把“窗口内最多两类元素”这个约束包装成了摘水果的故事本质上还是在考你是否真的理解窗口何时收缩、收缩到什么程度、以及为什么右指针不用回退。把这几个问题想清楚滑动窗口系列的大部分题目都能迎刃而解。我个人在实际刷题中的一个体会是不要背模板要理解窗口合法性的单调性。每次遇到窗口类题目先在纸上画一画问自己三个问题——右指针右移时窗口合法性是变好还是变差左指针右移时窗口合法性是变好还是变差什么时候需要更新答案想清楚这三个问题代码基本就是按部就班地写。最后分享一个小技巧刷完一道滑动窗口题试着把窗口内最多元素个数从2改成K看代码要改几行。如果只需要改一个数字说明你对这个模板的理解到位了。我每次讲这道题给朋友听都会让他们现场做这个改动大部分人改完就通了。有些题目包装得很花哨但拆开看核心就是那几行代码水果成篮恰恰是那双指针领域最值得反复咀嚼的入口题之一。 
长河君 · 2026/9/7 20:17:26 · 阅读 1.2k 水果成篮leetcode904滑动窗口双指针详解：从原理到代码实践
看到“水果成篮”这个题目很多刷题的朋友第一反应是“这不就是个滑动窗口嘛”但真上手写的时候边界条件、窗口收缩时机、计数器的维护处处都是坑。这道题在力扣上是904号属于双指针专题里非常经典的一道“窗口内最多包含两类元素”的题目和“无重复字符的最长子串”并列为滑动窗口入门必刷题。今天这篇就以它为例把双指针的解题思路、代码细节、易错点一次说透顺便聊聊双指针的另一类应用——合并有序数组帮大家把这类题串成一条线。1. 题目到底在问什么读题与核心矛盾拆解1.1 场景还原与题意转化先别急着想算法我们把题面翻译成人话。你是一片果园的采摘工面前有一排果树每棵树上结的果子都有一种类型用数组里的数字表示比如[1,2,1]表示三棵树的果子类型分别是1号、2号、1号。你手里只有两个篮子每个篮子只能装同一种类型的果子也就是说你最多同时收集两种类型的果子。你从某棵树开始摘可以一路往右摘但只要你遇到的果子类型是第三种就必须停下来。问从哪棵开始摘能摘到最多的果子换成一个纯算法的说法给定一个整数数组fruits找出一个最长的连续子数组使得这个子数组中不同数字的个数不超过2返回这个子数组的长度。这两句话等价但第一句话更容易建立直觉。举个例子fruits [3,3,3,1,2,1,1,2,3,3,4]从第一个3开始摘能摘[3,3,3,1]吗能因为只有3和1两种类型。还能往里走吗下一个是2第三种类型不能要了。那从第四个元素1开始呢可以摘[1,2,1,1,2]长度为5。我们要的就是所有可能起点里能摘到的最长长度。题目要求的答案就是无论从哪棵树开始用两个篮子能收集到的最大水果数量。注意篮子里的水果类型一旦确定中途不能换但我们可以选择在任意一棵树开始这就是“贪婪的采摘者”这个名字的由来——采摘者只顾着尽可能多摘能摘就摘遇到第三种类型就止损。很多新手在这里会误解成“找数组里出现次数最多的两种数字的总出现次数”这是不对的。因为采摘必须是连续的中间不能跳过某棵树所以本质是“连续子数组”而不是“全局统计”。我当初就被这个误解坑过写完代码跑测试用例发现结果偏大才反应过来连续性这个约束有多重要。1.2 为什么这题适合用双指针既然要找一个连续区间而且区间内的“不同元素个数”这个条件会随着区间的伸缩而变化那自然能想到用双指针维护一个动态窗口。窗口的左边界和右边界分别对应采摘的起点和当前到达的位置窗口内始终满足“不同水果类型不超过2”这个约束。右指针负责扩张尽可能多摘左指针负责在约束被破坏时收缩换一个起点。整个过程下来每个元素被右指针扫过一次、被左指针扫过一次总时间复杂度O(n)空间复杂度O(1)如果用一个固定大小的计数数组或O(k)k是水果类型数如果用哈希表。对比一下暴力解法枚举所有起点i和终点j检查子数组fruits[i..j]中不同数字个数是否不超过2复杂度O(n²)甚至O(n³)如果检查函数遍历子数组在n达到10⁵量级时直接超时。双指针滑动窗口正是针对“连续子数组 某种动态约束”这类问题的最优解模板。2. 从暴力到滑动窗口思路演进与方案选型2.1 暴力解法先写出来再谈优化我刷题的习惯是拿到一道中等难度的题先别急着套模板先把最朴素的想法写出来哪怕超时至少能验证自己对题意的理解是否正确。对于“水果成篮”暴力解法非常简单public int totalFruit(int[] fruits) { int n fruits.length; int ans 0; for (int i 0; i n; i) { for (int j i; j n; j) { // 统计 fruits[i..j] 中不同数字的个数 if (countDistinct(fruits, i, j) 2) { ans Math.max(ans, j - i 1); } } } return ans; }其中countDistinct可以用一个HashSet实现。但这样做时间复杂度是O(n³)因为两层循环加每次统计都要遍历子数组。哪怕把统计优化成在第二层循环里动态维护一个HashMap复杂度降到O(n²)对n 10⁵的数据来说依然不可接受。暴力解法的意义不在效率在于帮我们确认一个关键事实答案一定是某个连续子数组的长度。有了这个认知就能进一步想有没有办法不枚举所有起点而是用一个“会移动的窗口”去扫一遍数组。2.2 滑动窗口的可行性分析为什么滑动窗口在这道题里是对的关键在于一个性质如果fruits[i..j]是一个合法的子数组不同元素不超过2那么它的任意子数组fruits[i1..j]也一定是合法的删除元素不会让不同元素个数变多。反过来如果fruits[i..j]不合法那么fruits[i..j1]也一定不合法加入元素不会让不同元素个数变少。这个性质叫做“单调性”——窗口的合法性随着右指针右移单调变差随着左指针右移单调变好。正是这个单调性让我们可以在右指针扩张到不合法时通过不断移动左指针来重新让窗口合法而不需要回退右指针。右指针不回退整体就是线性扫描这就是滑动窗口能保证O(n)复杂度的根本原因。如果题目换成“找出一个最长的子数组其中不同元素的个数恰好等于2”那单调性就被破坏了滑动窗口模板就不太好用需要额外处理恰好等于的情况。所以在动笔之前先确认约束是否满足单调性能省掉很多debug时间。3. 核心实现代码逐行拆解与参数细节3.1 Java实现计数器数组 or 哈希表水果的类型是整数而且题目一般会说0 fruits[i] fruits.length所以可以直接用一个长度等于fruits.length的数组作为计数器每次访问都是O(1)空间也是O(n)。如果类型范围未知或很大用HashMapInteger, Integer更稳妥。两种方案本质一样下面给出用数组实现的版本public int totalFruit(int[] fruits) { int n fruits.length; int[] count new int[n]; int left 0; int ans 0; int kinds 0; // 当前窗口内有几种不同的水果 for (int right 0; right n; right) { // 1. 扩张把 fruits[right] 加入窗口 if (count[fruits[right]] 0) { kinds; } count[fruits[right]]; // 2. 收缩如果类型数超过2移动左指针 while (kinds 2) { count[fruits[left]]--; if (count[fruits[left]] 0) { kinds--; } left; } // 3. 此刻窗口 [left..right] 一定合法更新答案 ans Math.max(ans, right - left 1); } return ans; }注意几个关键变量count[]记录窗口内每种水果的剩余数量kinds记录窗口内有几种不同的水果它和count数组配合避免每次判断种类数时都遍历countleft是窗口左边界right是右边界ans记录历史最大窗口长度。当while (kinds 2)收缩时每移动一次left都要把对应水果的计数减一如果减到0说明这种水果在窗口里没了kinds减一。这个while循环可能会执行多次直到窗口重新合法为止。为什么这里用while而不是if因为只移一个左边界可能不足以消除第三种水果。举个例子fruits [1,1,1,2,3]right指向3时窗口是[1,1,1,2,3]包含3种水果需要一直把左指针移过所有1窗口变成[2,3]才重新合法。用if只移一步窗口变成[1,1,2,3]依然不合法就会出错。3.2 代码的等价写法for循环 while字典版如果你更喜欢用HashMap写逻辑完全一样只是更新方式略有不同public int totalFruit(int[] fruits) { MapInteger, Integer basket new HashMap(); int left 0; int ans 0; for (int right 0; right fruits.length; right) { basket.merge(fruits[right], 1, Integer::sum); while (basket.size() 2) { basket.merge(fruits[left], -1, Integer::sum); if (basket.get(fruits[left]) 0) { basket.remove(fruits[left]); } left; } ans Math.max(ans, right - left 1); } return ans; }两种写法性能差别不大用数组统计在整数范围可控时稍快一点点用HashMap则更通用。我建议面试时先写HashMap版本因为它能自然处理类型范围不确定的情况如果面试官要求优化空间再改成数组计数器。3.3 边界条件与极端用例这类题最容易翻车的就是边界条件。我总结了几组必测的用例建议写完代码后立刻跑一遍输入期望输出解释[1]1只有一个篮子都需要时输出1[1,2]2正好两种水果全摘[1,2,1]3两种水果交替出现窗口可以持续扩张[1,2,3]2三种水果最多只能摘前两个或后两个[3,3,3,1,2,1,1,2,3,3,4]5经典用例答案来自[1,2,1,1,2][0,1,2,2]3答案来自[1,2,2]或[0,1]注意窗口收缩的时机跑这几个用例基本能覆盖“窗口从未超两类”“窗口超两类需要收缩多次”“窗口收缩到只剩一种类型”等核心场景。我每次写完滑动窗口的题都会把这类用例粘贴到本地里做回归这比在提交后等判题反馈要快得多。4. 手推全过程从3种水果回退到2种4.1 逐步推导一次完整扫描为了更直观理解左指针的收缩过程我们用手推一遍fruits [1,2,1,3,1]。初始left 0,right 0,count[1] 1,kinds 1, 窗口[1]合法ans 1。right 1加入2count[2] 1,kinds 2, 窗口[1,2]合法ans 2。right 2加入1count[1] 2,kinds不变仍为2窗口[1,2,1]合法ans 3。right 3加入3count[3] 1,kinds 3超了。进入while移动left从0到1count[1]从2降到1不为0kinds仍为3窗口[2,1,3]还是不合法移动left从1到2count[2]从1降到0kinds降到2窗口[1,3]合法停止收缩。此时ans Math.max(3, 4 - 2 1) 3。窗口内是[1,3]虽然长度只有2但后续可能扩展到更大。right 4加入1count[1] 2,kinds不变为2窗口[1,3,1]合法ans Math.max(3, 5 - 2) 3。最终答案是3最长子数组是[1,2,1]或[1,3,1]。手动推一遍就会发现整个扫描过程中right从来没回退过这就是“双指针/滑动窗口”的核心优势。4.2 为什么right不需要回退很多第一次接触滑动窗口的人都会问左指针收缩之后右指针为什么不用回到新的左指针位置重新扫原因就是前面提到的单调性。右指针扫过的区域里如果某个窗口不合法那么把它左边界右移后一旦重新合法新的合法窗口的右边界只会比原来的右边界更靠右或相等不会在更左边出现一个更优的合法窗口。换句话说我们已经“错过”的左边界所构成的窗口长度都不会超过当前记录的最优值所以直接让右指针继续往右扫不会漏掉答案。这个思想非常重要它是滑动窗口系列所有题目的基石。理解了这一点以后遇到“最长无重复子串”“最长连续1的个数最多K个0”这类题都能一眼看穿套路。5. 常见问题与排查技巧实录5.1 典型Bug忘记把计数减到0时种类数减一这是我见过最多人犯的错。如果收缩左指针时只执行count[fruits[left]]--而没有在计数变为0的时候同步kinds--那么kinds会一直虚高导致窗口明明已经合法了程序还认为不合法窗口过度收缩答案偏小。错误版代码长这样while (kinds 2) { count[fruits[left]]--; left; // 忘了 if (count[fruits[left]] 0) kinds--; }排查方法非常简单在while循环里打印left、right、kinds和count数组一眼就能看出kinds是不是该减没减。用我上面给的手推用例[1,2,1,3,1]跑一遍right3时就会发现问题。5.2 典型Bugans更新位置不对另一个常见错误是把ans Math.max(ans, right - left 1)写在while收缩之前。这样在窗口不合法的时候也会尝试更新答案可能把不合法的窗口长度记录进去。比如窗口[1,2,3]长度是3但它并不合法正确的最优解可能是2如果不小心记录了3答案就错了。正确做法是先通过while把窗口收缩到合法状态再更新答案。窗口合法的时机就是while循环结束后因为此时kinds 2且left是满足条件的最小左边界收缩得最狠长度right - left 1是右边界固定为right时的最大合法窗口长度。5.3 实战排查技巧加日志跑用例遇到答案不对不要干瞪眼。我的习惯是在关键位置加上临时日志for (int right 0; right n; right) { // 加入 fruits[right] System.out.println(right right , 加入 fruits[right]); while (kinds 2) { System.out.println( 收缩: left left , 移除 fruits[left]); // ... } System.out.println( 窗口: [ left , right ], kinds kinds); }跑一遍小规模用例看窗口的移动轨迹是否符合预期。大多数时候问题都出在“窗口的收缩没有把kinds同步更新”或者“更新ans的位置不对”这两个点上。5.4 一个微妙的小优化外层用for还是while在滑动窗口的标准写法里外层通常用for (int right 0; right n; right)每一步右指针固定前移一步。这样写的优点是逻辑清晰right的移动次数固定为n时间复杂度好分析。也有用while (right n)配合内部right的写法效果一样但代码稍显啰嗦而且容易忘记在分支里更新right造成死循环。我建议一直用for循环写外层减少心智负担。另外一个常见优化是提前退出如果当前剩余数组长度已经不可能超过ans可以提前break。比如ans n - left就可以退出。这个优化对实际性能提升有限但在极端用例下可以省一点点时间if (ans n - left) break;不过要注意这个退出判断要放在每次更新ans之后否则可能提前退出错过更优解。6. 变体与延伸从两篮到K篮以及双指针的另一副面孔6.1 泛化版本最多K种不同水果“水果成篮”最常见的变体是把两个篮子改成K个篮子即求“最长连续子数组其中不同元素个数不超过K”。代码只需要把kinds 2改成kinds K其他完全不用变。这也是力扣340题“至多包含 K 个不同字符的最长子串”的解法。所以“水果成篮”其实就是“K2”的特殊情况。遇到这种泛化题目我建议把K作为一个参数传入函数这样不仅代码复用度高面试时还能展示你对题目的抽象能力。比如public int totalFruit(int[] fruits, int k) { // 逻辑不变把 2 换成 k }6.2 双指针的另一类应用合并有序数组如果说滑动窗口是“同向双指针”那么合并有序数组用的就是“相向或分头推进的双指针”。拿“合并两个有序数组”来说经典做法是三个指针一个指向第一个数组的有效末尾一个指向第二个数组的末尾一个指向合并后数组的末尾从后往前填。这个思路和滑动窗口的区别在于两个指针不是在维护同一个窗口而是在两个数组上各走各的比大小、填结果。比如nums1 [1,2,3,0,0,0],nums2 [2,5,6]从后往前比较大的放到nums1末尾。这个操作之所以能用双指针是因为两个数组分别有序每次比较都可以确定一个元素最终放哪不会破坏有序性。很多初学者一看到“双指针”就先想滑动窗口其实双指针的应用远不止“窗口”一种形态。理解“同向”“相向”“分类讨论”这些不同模式才是真正掌握双指针的关键。6.3 刷题路径建议如果你正在系统刷双指针我的建议顺序是同向双指针滑动窗口先刷“无重复字符的最长子串”再刷“水果成篮”然后刷“最小覆盖子串”和“字符串的排列”相向双指针先刷“两数之和 II - 输入有序数组”再刷“三数之和”“盛最多水的容器”分头推进双指针刷“合并两个有序数组”“合并两个有序链表”“寻找两个正序数组的中位数”。这样按“模式”刷题比按题目难度刷更高效因为同一个模式的题核心套路是通用的每刷一道都在加深对这类题的理解。7. 写在最后的几点实在体会说实话“水果成篮”这道题本身的难度并不高但它是一道特别好的“滑动窗口教学题”。因为它把“窗口内最多两类元素”这个约束包装成了摘水果的故事本质上还是在考你是否真的理解窗口何时收缩、收缩到什么程度、以及为什么右指针不用回退。把这几个问题想清楚滑动窗口系列的大部分题目都能迎刃而解。我个人在实际刷题中的一个体会是不要背模板要理解窗口合法性的单调性。每次遇到窗口类题目先在纸上画一画问自己三个问题——右指针右移时窗口合法性是变好还是变差左指针右移时窗口合法性是变好还是变差什么时候需要更新答案想清楚这三个问题代码基本就是按部就班地写。最后分享一个小技巧刷完一道滑动窗口题试着把窗口内最多元素个数从2改成K看代码要改几行。如果只需要改一个数字说明你对这个模板的理解到位了。我每次讲这道题给朋友听都会让他们现场做这个改动大部分人改完就通了。有些题目包装得很花哨但拆开看核心就是那几行代码水果成篮恰恰是那双指针领域最值得反复咀嚼的入口题之一。