1. 项目概述先搞懂“颜色分类”这道题想考什么LeetCode 热题 100 的第 75 题“颜色分类”Sort Colors大概是所有求职者避不开的一道经典题。题目本身不长给你一个只包含0、1、2的整数数组分别代表红色、白色、蓝色要求把它们原地排序成0、1、2的顺序排列。题目光看表面会觉得很简单——“不就排个序吗sort 一下不就完了”。但这道题真正要考察的恰恰不是你会不会调sort而是三件事数组遍历的指针设计、原地交换的边界控制、以及你能否识别出它其实是经典“荷兰国旗问题”。面试官想看到的是你能不能在线性时间和常数空间内解决它而不是依赖 STL 或者额外开一个数组。我在实际刷题和整理面试题的过程中见过太多人栽在这道题上有人上来直接nums.sort()被追问一句“如果你不能用内置排序怎么办”就卡住也有人知道要双指针但交换逻辑写得漏洞百出最后在某些测试用例上翻车。这其实反映出一个普遍问题光知道“双指针”四个字不够你必须真正理解每个指针的含义和每一步交换的后果。这篇文章会把75. 颜色分类从题目本质、推导思路、三种解法的完整代码、边界调试到变体延伸一次讲透让不管是第一次刷题的新手还是准备面试冲刺的老手都能从这里拿走一份可以直接复用的解题模板。废话不多说先从题目本身拆起。1.1 核心需求解析题目还原与条件限制原题描述大致是这样一个长度为n的数组nums里面只有0、1、2三种元素要求原地排序使得数组变成“所有 0 在最前面所有 1 在中间所有 2 在最后面”。注意几个关键约束你只能原地修改数组不能额外开一个数组来计数字符然后回填。高级要求是一趟扫描one-pass完成时间复杂度O(n)空间复杂度O(1)。元素只有三类这在很多排序问题里属于特殊结构不能用常规排序的思维去套。举个最简单的例子nums [2,0,2,1,1,0]排序后应该变成[0,0,1,1,2,2]。这里有一个初学者最容易忽略的点题目要求的是“原地”所以一切引入新数组的做法即使思路正确也天然失分。面试里一旦你说“我准备先统计 0、1、2 的个数再重新填回原数组”“数组是会变的你统计完数字之后确实可以填但这就是破坏原题的意图——第一它不是原地第二这也埋下了“如果是其他类型数据就没法排序”的隐患。”1.2 为什么说它是荷兰国旗问题的变体荷兰国旗问题Dutch National Flag Problem由计算机科学家 Dijkstra 提出问题的背景是有红、白、蓝三色旗子乱序排列要求把它们按颜色排成红、白、蓝的顺序并且只能用一次遍历和常数空间。这正是75. 颜色分类的原型。为什么这个模型特别经典因为它代表了“三态分区”这一类问题。常见的快速排序里的三路划分3-way partition处理排序数组里大量重复元素时就是把数组分成 pivot、 pivot、 pivot三个区域。颜色分类本质上就是在做一个特殊的三路划分pivot 1所有小于 1 的放左边大于 1 的放右边等于 1 的放中间。所以你一旦掌握了荷兰国旗的模板后面遇到快排优化题、三指针分区题都能直接迁移。2. 思路演进从无知到最优解的三层递进刷题最重要的不是背答案而是建立一条从暴力到最优的推导链。你自己能推理出来面试时才能应对追问。这里我按我的理解把思路分成三个层次。2.1 第一层敢想“暴力法”——桶计数回填最直观的思路是既然元素只有0, 1, 2三类那我数一下每个类有多少个然后按顺序填回去。def sortColors(nums): counts [0, 0, 0] for x in nums: counts[x] 1 idx 0 for val in range(3): for _ in range(counts[val]): nums[idx] val idx 1这个解法的时间复杂度是O(n)空间复杂度O(1)如果硬说 counts 是常数大小的数组。但它要遍历两遍数组第一遍计数第二遍回填。在面试里如果你先给出这个解法作为“baseline”有经验的面试官会接着问你能不能一遍扫描就完成这就自然过渡到双指针解法。而且从工程角度批评这个方案的话它完全依赖元素的“值”恰好是0,1,2这个连续整数一旦换成其他枚举类型就不具备通用性。但作为解题的第一版它至少能帮你快速验证自己是否理解题意。我在面试过别人的过程中经常发现一个现象很多人连这个“笨办法”都写不顺比如统计之后忘了把idx归零或者第二层循环忘了把val和index区分开。所以我会建议哪怕是暴力解法也要当成真正要提交的代码来写变量命名要清晰。2.2 第二层双指针计数思想的雏形——两遍扫描优化版那能不能不统计、直接用交换可以。先想一个弱化版的问题如果只需把 0 放到最前面2 放到最后面1 留在中间那么可以用左右两个指针左指针left指向当前已排好 0 的边界初始为 0。右指针right指向当前已排好 2 的边界初始为n-1。用一个遍历指针i扫描数组。从左到右扫描的时候如果nums[i] 0就和nums[left]交换lefti如果nums[i] 2就和nums[right]交换right--但注意此时i不能急着加一因为换回来的新值还没检查如果nums[i] 1直接i。这里加了个“如果”——你看这其实就是完整的荷兰国旗解法。所以第二层思路并不需要单独写代码它其实是通往第三层的桥梁。关键在于理解“为什么nums[i] 2交换后不能加一”这是几乎所有 bug 的源头。2.3 第三层最优解——一遍扫描三指针交换荷兰国旗三色旗结构最终版解法里其实有四个变量left、right、i外加一个数组本身。它们各有清晰的职责left指向“下一个 0 应该放的位置”它左边不含 left的区域全部是 0。right指向“下一个 2 应该放的位置”它右边不含 right的区域全部是 2。i是当前遍历指针它负责一路扫过那些“待处理”的元素。数组的中间区域[left, i)全部是 1(right, n-1]全部是 2[i, right]是未处理的乱序区域。这个结构非常像一条流水线左边是已经处理完的 0 区中间是 1 区再往右是未知区最右边是 2 区。每一步都在把未知区变短直到i right时所有未知区域清空排序自然完成。很多资料里把这个算法总结为一句口诀“遇 0 换左遇 2 换右遇 1 不动。”但我个人不太建议只背口诀不画图因为一旦你离开纸笔、面对手撕代码环节很容易搞混 left 和 i 要不要同时前进。后面我会专门画一张执行轨迹表把每一步的数据变化梳理一遍。3. 核心实现三种解法的完整代码与执行轨迹我这里会给出三种语言的实现示例重点放在 Python 和 Java 上因为面试中这两门语言出现频率最高。代码都基于 LeetCode 官方判题的标准函数签名来写。3.1 基础版用 Python 实现计数回填先从这个最容易理解的版本开始。它虽不是最优但适合用来验证思路、跑通测试。def sortColors(nums): count0 count1 count2 0 for num in nums: if num 0: count0 1 elif num 1: count1 1 else: count2 1 idx 0 for _ in range(count0): nums[idx] 0 idx 1 for _ in range(count1): nums[idx] 1 idx 1 for _ in range(count2): nums[idx] 2 idx 1注意一个细节计数回填法虽然简单但它的前提是数组只会出现0,1,2一旦题目改成“包含其他任意值”这个方案就直接报废。所以它只能作为热身不能作为最终提交到面试的答案。但也不要小看它如果你在压力面时脑袋一片空白写一个能过的版本保底总比卡在那里不出代码要好。3.2 进阶版Java 实现一遍扫描三指针现在写核心的三指针解法。我要先给你一个完整的 Java 版本再逐行拆解。public void sortColors(int[] nums) { int left 0, right nums.length - 1; int i 0; while (i right) { if (nums[i] 0) { swap(nums, left, i); left; i; } else if (nums[i] 2) { swap(nums, right, i); right--; } else { i; } } } private void swap(int[] nums, int a, int b) { int tmp nums[a]; nums[a] nums[b]; nums[b] tmp; }这段代码看起来只有十几行但其实每个分支都有讲究。我把容易错的地方提前挑出来说while (i right)的边界条件是而不是。为什么因为当i right时最后一个位置还没有被处理必须循环到i right 1才能结束如果用最后一个元素永远不会进循环。nums[i] 0分支里交换后i因为left左边都是 0left指向的位置要么是i本身前面全是 1要么是已经遍历过的位置所以换过来的值不可能再是 2可以放心前进。nums[i] 2分支里交换后不i因为从right换过来的值是未知的可能是 0可能是 1还可能是 2必须留在原地再检查一次。nums[i] 1直接i1 本来就应该留在中间不需要交换。这个解法的时间复杂度是严格O(n)因为每个元素最多被访问常数次空间复杂度O(1)仅用了几个指针变量。正是题目要求的“一趟扫描 常数空间”。3.3 最佳实践遍历过程静态推演我觉得光给代码不够必须推演一遍才能真正理解指针为什么这样移动。拿nums [2,0,2,1,1,0]举例初始状态left0, i0, right5。步骤当前数组leftrighti动作说明初始[2,0,2,1,1,0]050-1[0,0,2,1,1,2]040nums[0]2与 right 交换right--2[0,0,2,1,1,2]040nums[0]0与 left 交换lefti3[0,0,2,1,1,2]141nums[1]0与 left 交换lefti4[0,0,2,1,1,2]242nums[2]2与 right 交换right--5[0,0,1,1,2,2]232nums[2]1i6[0,0,1,1,2,2]233nums[3]1i循环结束我特意没有简化表格因为亲手一步步推演比看十行解释更有效。你注意第 4 步交换后i仍然是 2而此时nums[2]变成了 2被交换出来的 2 移动到了right3指向的位置正确。如果你在交换 2 之后错误地执行了i就会跳过这个未知元素后面还要再处理甚至可能引发越界。3.4 另一种优雅写法Python 一行版与划分为 “0 区 1 区 2 区”用 Python 写同样逻辑时很多老手会稍微压缩一下代码但我建议面试时还是写得展开一点方便解释。这里给一个简洁但可读的版本def sortColors(nums): left, right 0, len(nums) - 1 i 0 while i right: if nums[i] 0: nums[left], nums[i] nums[i], nums[left] left 1 i 1 elif nums[i] 2: nums[right], nums[i] nums[i], nums[right] right - 1 else: i 1有人调侃这道题的 Python 最短答案可以写成nums.sort()但面试官大概率不会满意。如果你想玩可以试试在一行里用推导式但那种写法只适合刷题自娱不适合面试展示——因为面试官想看的是你对指针逻辑的掌控而不是 Pythonic 魔法。4. 避坑指南最常见的 bug 与调试实录这段是我最想写的部分。我在无数次的手撕代码环节里看到过各种千奇百怪的错误版本也曾经自己在买菜时对着数组走神推演。以下问题几乎每个刷这道题的人迟早都会碰到。4.1 指针边界为什么循环写i right而不是i right这是最经典的边界问题。假设数组是[1,1,2]left0, right2, i0nums[0]1i变成 1。nums[1]1i变成 2。此时i2若循环条件是i right2 2为假循环直接退出nums[2]永远没被处理数组是错的。而i right时还会进入循环发现nums[2]2与right交换right--变成 1此时i2 right1退出正确。所以记住i必须能访问到right指向的那个位置否则最后一个元素会被遗漏。4.2 交换 0 和交换 2 的不对称性我见过一个高频率 bug有人写两个分支都交换后i结果排序结果不稳定地错。下面这个版本就是典型错误# 错误示例交换 2 后 i 导致跳过检查 while i right: if nums[i] 0: nums[left], nums[i] nums[i], nums[left] left 1 i 1 elif nums[i] 2: nums[right], nums[i] nums[i], nums[right] right - 1 i 1 # 这里错了 else: i 1用nums [2,1,0]测试i0交换 2 后数组变[0,1,2]right变 1i错误地变成 1跳过检查nums[0]0最后数组是[0,1,2]表面看着正确换nums [2,0,1]再试i0交换 2 后数组变[1,0,2]right1i变成 1此时检查[1,0,2]中nums[1]0交换到 left 变[0,1,2]似乎也碰巧对了。那如果换nums[2,2,1,0]呢用错误版本跑i0交换 2 到末尾数组[0,2,1,2]right2i 变 1。i1数组[0,2,1,2]nums[1]2交换到 right数组[0,1,2,2]right1i 变 2。此时i2 right1循环退出输出[0,1,2,2]看似正确。但换个用例[0,2,1,2]注意这里开头的 0 被错误地换到 left然后 i初始 i0nums[0]0交换后不变left1, i1。i1nums[1]2交换到 right数组[0,1,2,2]right2i 变成 2。循环继续22nums[2]2交换到 right数组[0,1,2,2]right1i 变成 3。此时 i3 right1退出输出[0,1,2,2]仍然碰巧正确。这其实是一种“碰巧正确”的诱惑——有些错误版本在某些用例下会给出正确结果但在另一些用例下会翻车。比如[2,0,1,2]i0nums[0]2交换到 right数组[1,0,2,2]right2i 变成 1。i1nums[1]0交换到 left0数组[0,1,2,2]left1i2。此时 i2right2循环继续nums[2]2交换后 right1i3退出正确。老实说我甚至找不出一个稳定翻车的反例。但你敢在面试中赌这个吗赌输了就全盘皆输。关键是逻辑上你无法证明交换 2 后i是安全的所以工程上必须不带i。面试官问“为什么”的时候你要能说出“换回来的值未知需要留待检查”这句话。4.3 特殊情况全零、全二、空数组全 0[0,0,0]left 一路推进i 一路推进right 不动结果正确。全 2[2,2,2]每次交换 2 到 rightright 递减i 不变直到i0, right-1退出正确。空数组left0, right-1while (i right)即0 -1为假直接退出正确。单个元素直接退出或直接走一个分支只要边界条件写对就没问题。我强调空数组的原因在于有些人的循环优化成while (i nums.length)遇到[0]时没问题但遇到[2,1]时可能把 2 换到右边界后又把 1 换走产生错误。最稳妥的还是标准的荷兰国旗循环。4.4 一个常见的调试技巧在所有交换处打日志如果你实在调不通最快的办法是在三处分支里各打一行日志打印i, left, right, nums[i]然后用 LeetCode 的示例数组走一遍。我当初学这道题时就是这样做的五分钟内就能定位到指针错位点。等到理解之后再把日志删掉。别否认调试打印的价值它在学习阶段比任何脑内推演都直观。5. 扩展与实战从颜色分类到更广的算法场景掌握了解法本身只是第一步。能够在后续题目里复用它才算真正学透。我记得有次在群里看一个同学做快排三路划分优化题卡了很久后来发现他其实完全可以用荷兰国旗的模板。所以这里我想把它的迁移场景列清楚。5.1 关联题目一移动零 (Move Zeroes)力扣 283 题“移动零”给定一个数组把非零元素移到前面保持它们的相对顺序所有 0 移到末尾。这题其实可以看成一道两色分类把数组分成“非 0 区”和“0 区”。用类似思想一个指针j记录非零区末尾遍历时遇到非零就交换到jj。def moveZeroes(nums): j 0 for i in range(len(nums)): if nums[i] ! 0: nums[i], nums[j] nums[j], nums[i] j 1可以对比颜色分类的三指针这题退化成两指针一快一慢本质是“分区思想”的简化版。如果你能独立把颜色分类迁移到移动零说明你已经理解了三态分区到二态分区的递进关系。5.2 关联题目二快速排序的三路划分标准快速排序中处理大量重复元素时经典的两路划分小于等于放左、大于放右会退化到O(n^2)。这时可以采用三路划分把数组分成 pivot、 pivot、 pivot三部分然后递归排序小于区和大于区。这几乎就是颜色分类的模板left表示“下一个小于 pivot 的元素放置位置”。right表示“下一个大于 pivot 的元素放置位置”。i扫描注意 pivot的不要交换留在中间。区别只是 pivot 不一定是固定值 1而是基准值。所以刷完颜色分类再去看快排优化、荷兰国旗分区你会觉得很多代码模板似曾相识。这也是我推荐优先掌握这道题的原因它是一系列分区算法的最小公共内核。5.3 关联题目三K 种颜色的泛化如果数组里有k种颜色值域0到k-1要求排序排列怎么办三指针不再适用因为分区不止三个。常见解法有两个方向方向一执行两遍扫描第一遍把最小的颜色归位第二遍处理剩余颜色复杂度 O(kn)。方向二用计数排序思维统计每个颜色的数量再回填复杂度 O(nk)。所以这道题的“单次遍历三指针”是特殊的k3优化版本。面试里如果往这个方向追问你要能说清楚为什么三指针不能直接推广到任意 k。5.4 工程启示什么时候该用“额外空间换时间”有人说颜色分类用计数排序最简单为什么非要执着于一遍扫描呢工程上如果数组规模不大、性能要求不高计数排序完全合理。但算法面试考的不是“这个场景下空间够用吗”而是训练你在资源受限时如何敏锐地找到常数空间的解法。这个思维习惯在实际系统里很有价值有时你不能开一个辅助数组不是因为空间不够而是因为数据量巨大、无法一次性载入内存有时是内存带宽受限宁可多走几轮循环也不愿意引入额外分配。我在写过一段时间工程代码后回过头来再看这道题体会更深了能写出O(n)时间O(1)空间的版本代表你在“原地修改”这件事上不会被变量枝枝节节绕晕这恰恰是处理大型数据流时的重要基本功。6. 总结与自测三道自测题帮你判断是否真懂了我不想用那种“综上所述”的收尾方式也不想堆术语。最后我想留三个自测题你可以拿它们检验自己是不是真的吃透了这道题。手写三指针解法并解释每个分支中指针的移动规则特别是交换2后为什么要保持i不动。口头描述一遍荷兰国旗的分区不变式循环过程中nums[0..left-1]0nums[left..i-1]1nums[right1..n-1]2验证一次[2,0,2,1,1,0]的每一步执行。尝试不使用三指针而是写一个两遍扫描的版本分析它为什么比三指针多一次遍历在什么场景下这种“多一次遍历”反而更好比如数据流场景里你可能还要统计其他信息。如果你能流畅完成这三题那么这道 Hot 100 题目对你来说就已经不是“背代码”而是真的属于你了。我个人的体会是算法题最忌讳光看不写、光写不想。每做一道题都应该问自己三个“为什么”为什么用这种数据结构为什么要这样处理边界为什么复杂度是这个量级。能回答上来才算真正学会。