滑动窗口思想详解：以“水果成篮”为例，从暴力到O(n)

作为一个刷了几年算法题、也面过不少候选人的老码农我一直觉得滑动窗口是算法面试里“性价比”最高的一类题型思想简单模板固定但变化起来又特别能考察基本功。今天不聊虚的直接拿一道经典题“水果成篮”LeetCode 904来拆透这个思想。这道题的本质就是在一个数组里找一段最长的连续子数组要求里面最多只包含两种不同取值——这类题用暴力法写起来很直观但一旦数据量上来就崩了而滑动窗口恰恰能把时间复杂度从 O(n²) 拉到 O(n)思路顺了之后代码几乎不会写错。这篇文章适合正在刷题准备面试的同学、对算法模板不熟的初学者以及想弄懂“窗口到底怎么伸缩”的人。我会把每一步的为什么都交代清楚再配合完整代码、用例推演和踩坑记录争取让你看完就能直接上手。1. 项目概述与核心思路拆解1.1 这个题到底在考什么“水果成篮”的题目描述讲的是一个人有两棵树每棵树上结一种水果他沿路摘果子但手里只能带两个篮子每个篮子只能装一种水果问题是问他最多能连续摘多少棵树。翻译成算法语言就是给你一个整数数组fruits其中fruits[i]表示第 i 棵树的水果种类你需要找到一个最长的连续子数组保证子数组里不同数字的个数不超过 2然后返回这个最长长度。我第一次看到这个题的时候第一反应是“这不就是双指针吗”但真上手才发现窗口边界的收缩时机、频率计数的维护方式任何一步搞错都可能让你算出来的长度虚高或者漏掉最优解。它考察的其实有三个点一是你能否从生活化的题目描述中抽象出“最多包含两种不同元素的最长连续子数组”这个数学模型二是你是否真正理解滑动窗口里左右指针各司其职、何时扩展何时收缩三是你是否能用合适的数据结构哈希表或数组计数来维护窗口内的元素分布。很多人一上来就套模板结果套出个死循环根源在于没搞清楚窗口的“合法条件”是什么。这道题的合法条件非常明确窗口内的不同元素个数 ≤ 2。所有伸缩动作都是围绕这个条件展开的。1.2 滑动窗口的核心思想滑动窗口本质上是一种“枚举所有右端点同时维护一个最优左端点”的优化技巧。想象你有一个可以变长变短的窗口右指针right负责向前扩张每走一步都会尝试把新元素纳入窗口左指针left负责在窗口不合法时收缩把左侧多余的元素挤出去直到窗口重新合法。整个过程像一条尺蠖在数组上蠕动右端先探路左端跟着调整始终保持窗口内部满足约束。为什么它能从 O(n²) 优化到 O(n)关键在于“单调性”。以这道题为例对于任意一个右端点right当窗口内元素超过两类时无论left怎么右移right固定时窗口都不可能变长所以我们必须把收缩动作当成“恢复合法性”的手段而不是“找最优解”的手段。更直白地说我们并不需要枚举所有区间只需要维护一个“当前截止到 right 的最长合法区间”而这个区间的起点一定是使得窗口合法且尽可能靠左的left。因为如果left再靠左就会导致窗口里出现三类水果那这个起点就是右端点固定时理论上最长的窗口。随着right不断右移所有可能的右端点都被覆盖到了最优解必然在其中。用生活化的类比来说就像你在小吃街逛摊手里最多只能端两杯饮料。你每走到一个新摊位就往手里加一杯如果发现手里出现了第三种饮料就必须把左手边最早买的那杯喝掉或扔掉直到手里又只剩两种饮料。走过的摊位数量里你端得最多的连续一段就是答案。这个过程中你不需要回头重新计算前面的组合因为右手是一直往前走的状态。1.3 为什么用哈希表而不是简单的计数数组这道题常见的实现方式有两种一种是HashMap或 Python 的dict记录每个元素出现的次数另一种是因为题目限定只有两类水果所以用两个变量也能做。我强烈建议先掌握哈希表版本因为它能平滑过渡到“最多允许 K 种不同元素”的泛化问题面试官随便改一下参数你也能应对。用哈希表的核心价值在于我们需要快速知道窗口内当前有几种不同的值以及某个值是否还存在。数组计数虽然在某些场景更快元素值范围可控时但用哈希表让逻辑更统一——每次right进入窗口就把对应计数加一如果这个 key 之前不存在说明新增了一个种类当left收缩移出元素时计数减一减到 0 就删除该 key此时种类数才能准确反映为len(map)。这样“窗口是否合法”的判断就直接变成了len(map) 2语义非常清晰。也许有人会问题目说了只有两类水果用两个变量记录种类 a 和种类 b 不就可以了吗确实可以但一旦遇到连续切换的情况比如序列是 1、2、1、2、3、2、3你会在“到底该丢哪一种”上纠结半天代码很容易出现边界分支错误。哈希表把这堆分支统一成了一个“减到 0 就删键”的操作既减少出错概率也让代码可读性高得多。2. 核心细节解析与实操要点2.1 完整模板拆解right 与 left 的分工标准模板长这样我先写一个最通用的版本再逐行拆解def totalFruit(fruits): n len(fruits) cnt {} left 0 ans 0 for right in range(n): cnt[fruits[right]] cnt.get(fruits[right], 0) 1 while len(cnt) 2: cnt[fruits[left]] - 1 if cnt[fruits[left]] 0: del cnt[fruits[left]] left 1 ans max(ans, right - left 1) return ans拆解下来核心就三步。第一步右指针扩张。每遍历一个新元素就把它加入哈希表同时更新计数。这里用dict.get(key, 0)是 Python 里非常常用的“取旧值无则取默认值”的写法第一次遇到某个种类时从 0 开始加 1之后每次在旧值基础上累加。第二步窗口非法时收缩左指针。while len(cnt) 2是关键判断只要种类数超过 2就一直移动left。注意顺序先把left指向的元素计数减 1再判断这个计数是不是已经归零归零就该删除这个 key最后才把left加 1。很多初学者会先把left 1再更新哈希表结果删错元素、索引错位窗口逻辑全乱。第三步更新答案。right - left 1是当前窗口长度因为left和right都是闭区间下标所以长度要加一。这里每次循环都更新一次没有关系并不会影响复杂度因为ans max(ans, ...)是 O(1) 操作。也可以把这一步移到 while 收缩结束后再执行那样更严谨因为收缩后的区间才是真正的合法窗口但即使放在外面因为非法窗口的长度一定不会超过合法窗口的历史最大值所以结果仍然正确。模板里放在外面是为了少一次缩进逻辑上也说得通。2.2 收缩窗口的判定条件与边界处理这道题里收缩条件是len(cnt) 2但它背后的原理值得多说两句。为什么不是 2因为刚好等于 2 时窗口是合法的正好是我们希望保留的状态只有超过 2 才需要“挤出”多余种类。如果写成你会发现窗口永远最多只有一种水果答案自然就错了。这是很经典的“边界条件差之毫厘结果谬以千里”的例子。还有一个细节cnt[fruits[left]] 0之后必须del cnt[fruits[left]]。如果不删除这个 key 会一直留在字典里虽然计数是 0但len(cnt)会把键的个数也算进去导致窗口永远收缩不干净。这个坑我在初学阶段踩过不止一次尤其是当题目改成“最多 K 种不同元素”时如果哈希表里残留着计数为 0 的键len(cnt)会虚高程序就会在错误的窗口长度中打转。至于边界情况老规矩先处理空数组如果fruits长度为 0答案直接是 0模板里ans初始值就是 0所以空数组也自然安全。另一种特殊情况是数组中只有一种元素那么窗口从头到尾都合法left不会移动ans最后会等于整个数组的长度这也符合直觉——只有一个种类两个篮子只用一个当然可以全摘完。2.3 时间复杂度和空间复杂度分析这套模板的时间复杂度是 O(n)。虽然代码里有个while循环看起来好像是两层循环但实际上left在整个过程中最多从 0 移动到 n-1每个元素最多被left移出一次整体是摊还 O(n)。right遍历一遍也是 O(n)。哈希表的读写操作平均是 O(1)所以总时间就是 O(n)。空间复杂度在最坏情况下是多少由于我们最多只允许窗口内出现两类水果计数但哈希表里最多也只会有两个 key——因为一旦出现第三个 keywhile 循环就会缩到只剩两个 key。所以哈希表的 size 最大值就是 2 1循环中瞬间状态可能到 3但整体稳定在 2 以内。严格来说空间复杂度是 O(1)因为种类数固定不超过 2。这也是这道题比较“温和”的原因之一它不需要额外维护复杂的数据结构一个字典打天下。3. 完整实操过程与代码实现3.1 基于 Python 的完整实现上面给出的代码已经可以直接跑通但我平时写题还会加一些防御性判断和提高可读性的写法比如把“最多两类”抽象成变量k 2这样面试官追问“如果是 K 种水果呢”时你只需要改一个数字。我实际提交用的版本如下def totalFruit(fruits): max_types 2 n len(fruits) cnt {} left 0 ans 0 for right, fruit in enumerate(fruits): cnt[fruit] cnt.get(fruit, 0) 1 while len(cnt) max_types: left_fruit fruits[left] cnt[left_fruit] - 1 if cnt[left_fruit] 0: del cnt[left_fruit] left 1 ans max(ans, right - left 1) return ans我在本地用一组随机测试数据跑过很多轮结果跟暴力法的标准答案完全一致。用一个例子fruits [3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4]手动推一遍最终答案是 5对应的子数组[2, 1, 1, 2, 3]实际上是 5 个元素却包含三类不对我再仔细检查一下[2, 1, 1, 2]是 4 个而[1, 1, 2, 3]包含三类。给我一点时间正确的整体答案是 5在这组数据里从下标 3 的 1 到下标 7 的 2 这一段的长度是 5元素是[1, 2, 1, 1, 2]只包含 1 和 2 两类完全合法。其他更长的区间比如 8 个元素都含有至少三类所以 5 就是答案。这个过程本身就体现了代码里ans max(ans, right - left 1)在每一轮都尝试抓取最长合法片段的作用。3.2 手把手推演一个测试用例拿一个简单的去重数组来推演fruits [1, 2, 1, 2, 3, 3, 3, 3]。初始cnt {}left 0ans 0。right 0水果 1 进入cnt {1:1}种类数 1 ≤ 2合法窗口长度0 - 0 1 1ans 1。right 1水果 2 进入cnt {1:1, 2:1}种类数 2合法窗口长度1 - 0 1 2ans 2。right 2水果 1 进入cnt {1:2, 2:1}种类数 2合法窗口长度 3ans 3。right 3水果 2 进入cnt {1:2, 2:2}种类数 2合法窗口长度 4ans 4。此时窗口是 [1,2,1,2]。right 4水果 3 进入cnt {1:2, 2:2, 3:1}种类数 3 2非法。进入 whileleft 0水果 1 出窗口cnt变成{1:1, 2:2, 3:1}left 1len(cnt)还是 3继续left 1水果 2 出窗口cnt变成{1:1, 2:1, 3:1}left 2len(cnt)还是 3继续left 2水果 1 出窗口cnt变成{2:1, 3:1}left 3此时len(cnt) 2退出 while。窗口是 [2,3]长度4 - 3 1 2ans仍是 4。right 5水果 3 进入cnt {2:1, 3:2}种类数 2窗口 [2,3,3]长度 3ans仍是 4。right 6水果 3 进入窗口 [2,3,3,3]长度 4ans仍是 4。right 7水果 3 进入窗口 [2,3,3,3,3]长度 5ans 5。最终输出 5。推演完你会发现窗口像一个“可变的取景框”它永远框住“以当前 right 为右端点的、最多包含两种水果的最长连续段”。只有当右指针带来第三类水果时取景框的左侧才会被迫放弃前面累积的水果这也是为什么这道题能保持 O(n) 的原因——左侧不会回头。3.3 其他语言的模板对照很多读者用的是 Java 或 C我顺手贴一下这两版的模板方便直接改写成自己熟悉的语言。Java 版本class Solution { public int totalFruit(int[] fruits) { int n fruits.length; MapInteger, Integer cnt new HashMap(); int left 0, ans 0; for (int right 0; right n; right) { cnt.put(fruits[right], cnt.getOrDefault(fruits[right], 0) 1); while (cnt.size() 2) { cnt.put(fruits[left], cnt.get(fruits[left]) - 1); if (cnt.get(fruits[left]) 0) { cnt.remove(fruits[left]); } left; } ans Math.max(ans, right - left 1); } return ans; } }C 版本class Solution { public: int totalFruit(vectorint fruits) { int n fruits.size(); unordered_mapint, int cnt; int left 0, ans 0; for (int right 0; right n; right) { cnt[fruits[right]]; while (cnt.size() 2) { if (--cnt[fruits[left]] 0) { cnt.erase(fruits[left]); } left; } ans max(ans, right - left 1); } return ans; } };C 里--cnt[fruits[left]] 0是一个很紧凑的写法先自减再判断是不是 0如果是就erase。注意如果不用if包住而是直接if (cnt[fruits[left]] 0)必须先自减再判断否则会漏删。这个简写在面试时写起来很快但需要在草稿纸上确认逻辑否则微妙的优先级问题容易让人当场翻车。模板统一这也是滑动窗口题型最大的魅力你只需要记住“右扩、收缩、更新”这三个动作剩下的全是细节打磨。4. 常见问题与排查技巧实录4.1 五个高频翻车现场第一窗口长度算成right - left而不是right - left 1。闭区间求元素个数必须加一这一点我自己刚学的时候几乎每次都错后来养成习惯凡是看到数组下标求长度先问自己是开区间还是闭区间。滑动窗口通常是闭区间因为两个指针都指向真实存在的元素。第二忘了在计数归零后删除 key。前面反复强调过len(cnt)计算的是键的数量而不是值的总和{1:0, 2:2}的len是 2但水果 1 实际已经不存在了如果窗口里现在只有水果 2你的哈希表却会告诉你还有两类窗口收缩条件永远无法触发结果自然不对。第三while len(cnt) 2写成if len(cnt) 2。滑动窗口的收缩必须是循环而不是一次判断。因为移出左侧一个元素后可能窗口里还是有三类水果比如窗口是[1, 2, 1, 2, 3]移出 1 后还有[2, 1, 2, 3]依然是三类必须一直收缩到合法为止。如果你只判断一次窗口就带着三类水果持续扩张最终答案显著偏大。第四在更新ans时使用了收缩前的窗口长度。说明一下用right - left 1放在right循环结束时如果前面有while收缩这个长度已经是收缩后的长度所以是对的。但如果你在外层循环开头就更新了ans还没执行收缩那时候窗口可能是非法的长度虽然看起来很大但实际不可用。所以更稳妥的写法是把ans更新放到 while 之后。虽然逻辑上即使放前面也不影响最终答案因为非法窗口的长度不会成为最优解但它会让代码的“意图表达”不清晰我自己练习时会刻意把更新答案的动作放在收缩之后。第五空数组或数组元素为零的极端情况。空数组直接返回 0而for right in range(n)不会执行ans保持 0这没问题。但如果你用fruits []跑 Java 版fruits[right]根本不会执行ans也是 0。就实际题目约束来说fruits.length 1所以空数组最多是本地测试时用。4.2 从“错误写法”到“正确写法”的对照我见过一个很典型的错误写法贴出来给大家看看def totalFruit(fruits): cnt {} left 0 ans 0 for right in range(len(fruits)): cnt[fruits[right]] cnt.get(fruits[right], 0) 1 if len(cnt) 2: cnt[fruits[left]] - 1 left 1 ans max(ans, right - left 1) return ans这个版本有三个问题收缩用了if而不是while对计数归零的 key 没有删除左指针移动前后没有同步清除计数为 0 的键。用[1, 2, 1, 2, 3]测试时到right 4时cnt {1:2, 2:2, 3:1}left从 0 变成 1但len(cnt)依然是 3然后ans 4 - 1 1 4看起来好像还凑合但再往后走就完全偏了。正确做法一定是while len(cnt) 2且在移出元素后判断是否删除 key。这里我建议初学者每次写完代码都手动用一个包含“连续两次引入第三类元素”的测试用例跑一遍比如[1, 2, 1, 2, 3, 4]基本上错误写法都会当场暴露。4.3 面试官追问如果允许 K 种水果呢我把这道题讲透之后通常面试官都会加一句“那如果现在你手里有 K 个篮子呢”这就是把“最多 2 类”泛化成“最多 K 类”。你只要把模板里的2改成K整个逻辑一字不改就能通过def totalFruit(fruits, k): cnt {} left 0 ans 0 for right in range(len(fruits)): cnt[fruits[right]] cnt.get(fruits[right], 0) 1 while len(cnt) k: cnt[fruits[left]] - 1 if cnt[fruits[left]] 0: del cnt[fruits[left]] left 1 ans max(ans, right - left 1) return ans这就是我一开始坚持让你用哈希表而不是两个变量的原因。面对变体题抽象得越通用你改动就越少。类似的变体还有“每个种类最多出现几次”“最长子数组且不同字符数不超过 K”等本质上都是维护一个哈希表加一个合法性判定模板不变变的只是 while 里的条件。平时练习时多想一想“条件改一改还能不能跑”比单纯背题有价值得多。5. 滑动窗口思想的应用延伸5.1 滑动窗口最大值与最小值除了这种“计数合法”的题型滑动窗口思想最常见的亲戚是“滑动窗口最大值”“滑动窗口最小值”系列LeetCode 239 就是求窗口大小为 k 的最大值。这里的难点是你需要在窗口不断右移的过程中快速知道当前窗口内的最大值暴力法是 O(n·k)但结合单调队列就能在 O(n) 内完成。具体做法是维护一个双端队列队列里的元素下标对应的值严格递减窗口右移时从队尾弹出比新元素小的下标从队头弹出已经滑出窗口的下标队头始终就是当前窗口最大值。这个思路和“水果成篮”看起来不太一样但本质上都是“用一个数据结构维护窗口状态让查询合法解变得高效”。学会了基础滑动窗口模板再看单调队列和单调栈就会容易很多因为你已经理解了“窗口状态需要被持续维护”这件事。5.2 滑动窗口中位数比最大值更难一点的是“滑动窗口中位数”。窗口大小固定为 k每次窗口右移一位你都要输出当前窗口的中位数。如果用暴力法每次排序窗口里的 k 个数时间是 O(n·k log k)明显不够看。常见的优化是维护两个堆一个大顶堆放较小的一半一个小顶堆放较大的一半并且保持两个堆的大小平衡中位数要么是堆顶要么是两个堆顶的平均数。窗口滑动时要删除离开窗口的元素这一步可以用延迟删除惰性删除实现节点虽然还在堆里但打上标记等它浮到堆顶时再真正弹出。这个题的复杂度是 O(n log k)它和水果成篮一样窗口都在“右扩”但窗口状态维护的数据结构从哈希表升级成了双堆。建议有兴趣的读者把这两个题放在一起做能明显感受到滑动窗口结合不同数据结构解决不同约束的威力。5.3 滑动窗口滤波与硬件实现热搜词里还有一些看着很硬核的比如“滑动窗口滤波”“滑动窗口滤波 verilog”。这其实说明滑动窗口不是算法面试专属它早就进入了工业界。简单来说滑动窗口滤波就是对一个连续信号序列取固定大小的窗口计算窗口内数据的均值或加权均值然后让窗口逐点滑动得到平滑后的输出。比如传感器采集到的温度数据总会有随机噪声用窗口大小为 5 的移动平均滤波就能明显削弱高频抖动。这个概念在数字信号处理里很常用在 Verilog 实现中通常会维护一个移位寄存器构成滑动窗口每个时钟周期移入一个新数据、移出一个旧数据再配合加法树或流水线结构高效计算窗口和避免每个周期都重新累加全部窗口数据。这类硬件实现的思路和我们在代码里维护cnt来减少重复计算非常像——算法优化的核心往往就是“不要每次都从头算而是增量维护状态”。理解这一点你会觉得滑动窗口不仅是一道面试题更是一种通用的计算思维。写在最后的体会说实话“水果成篮”这道题在 LeetCode 里的难度只是中等但它非常适合作为滑动窗口的入门题反复咀嚼。我自己每次给朋友讲算法专题都会先把这道题作为“窗口必须收缩才合法”的典型案例因为它比直接拿“最长无重复子串”讲更容易说明白“什么情况下窗口不合法以及为什么 while 而不是 if”。如果你正在刷题我建议不要只把这个模板背下来而是拿 10 组不同的数组手推一遍包括全相同、全不同、只有两个种类反复横跳、空数组这些边界情况手推一遍之后你对left的移动逻辑就会有肌肉记忆。等到面试时遇到“最多 K 种不同字符的最长子串”这类题你几乎可以不假思索地把模板默写出来然后改一行条件就够了。最后再分享一个小技巧写完代码后在纸上把left和right的每一次移动都画成“窗口快照”这个动作能帮你发现绝大多数自己看不出来的逻辑错误。