“颜色分类”这四个字只要你在LeetCode热题100里刷过一段时间就一定不会陌生。这道题在各个公司的笔试面试里出现频率高得离谱题面本身又简单得不像话一个数组里面只有0、1、2三种数字要求把它们原地排成0全部在前、1全部居中、2全部在后的形式。你可能会想这不就是三行代码的事儿吗但事情并没有这么简单。题目在“简单”的外表下藏着两个苛刻要求一趟遍历完成空间复杂度只能到常数级。这两个要求一加就把“直接调用排序函数”和“新开一个数组再填回去”这两条最省事的路全堵死了。面试官真正想看的是你有没有“用指针维护多个区间”的思维——这正是荷兰国旗问题的经典考察点也是把“排序”降维成“分类”的关键一步。这篇文章适合三类人第一次刷这道题、看完题解觉得“懂了但过两天又忘了”的初学者需要系统复盘高频面试题的老手以及想从一道具体题目提炼出一类通用解法的进阶玩家。我会把思路模型、代码实现、正确性证明、踩坑记录和面试追问一次讲透全程用我自己的实战口吻不绕弯子。1. 读题先读透三色数组的排序到底在考什么1.1 原地排序的限制为什么如此关键先看看题目本身。给你一个数组nums里面只有0、1、2三种数字要求把它们排成000...111...222...的形式。看起来简单但题目里藏着两个硬性限制第一只能在原数组上操作不允许开辟新的数组来辅助排序这就是“原地”第二一般情况下还会要求一趟遍历完成也就是说你只能顺着数组走一遍走完排序就结束。很多人刷这道题时第一反应是“那我直接调用排序函数不就行了”在面试里这个回答不算错但拿不到加分点。原因有两个一是内置排序的时间复杂度是O(n log n)而这个数组只有三种元素信息熵低到离谱用通用排序算法属于杀鸡用牛刀二是题目考察的本质并不是“排序”而是“分区”。换句话说面试官想看的是你能不能利用“只有三个值”这个条件把问题从“排序”降维成“分类”。我见过不少刚开始刷题的朋友卡就卡在没意识到“原地”这两个字的重量。原地意味着你没法用哈希表统计完再新开一个数组回写虽然这样也能过也意味着你没法用归并排序那套“临时数组合并”的玩法。你手里的资源只有数组本身和几个变量这其实是在逼你思考怎么用最少的额外空间完成一遍扫描就归位所有元素。1.2 先算一笔账直接排序和计数排序的代价在动笔写三指针之前先聊聊两个过渡方案搞懂它们为什么不够好你才能真正理解三指针方案妙在哪里。第一个方案是直接调用库函数排序。假设数组长度是n库函数排序的时间复杂度是O(n log n)对于只有三种取值的数组这个复杂度显然是浪费的。更关键的是这种做法完全没有利用“只有0、1、2”这个关键信息属于通用解法面试官如果要考察你的算法思维这种答案基本不会让对话继续下去。第二个方案是计数排序分两步走第一遍遍历统计0、1、2出现的次数第二遍遍历按统计结果把数组回填。时间复杂度O(n)空间复杂度O(1)这个方案其实已经不错了如果你在面试中实在想不出三指针方案退而求其次写计数排序也能过大部分面试。但它的“软肋”是需要遍历两遍。题目既然明确要求一趟扫描两遍遍历就不算最优解。所以最终目标很明确一趟遍历常数空间就地完成三类元素的归类。这一点恰恰是荷兰国旗问题的核心场景——用三个指针把数组切成三块每块同色。接下来要讲的三指针方案就是冲这个目标去的。2. 三指针分区法一趟遍历的思维模型2.1 三个指针各管一段区间划分的核心思想三指针方案的思想可以归结为一句话用三个指针维护数组的四个区间。听着玄乎其实就是一个“画线分块”的游戏。定义三个变量left、cur、right。初始时left0cur0rightn-1。在整个算法运行过程中它们始终维护以下四个区间[0, left)已经处理好的0全部归位在数组最前面[left, cur)已经处理好的1紧跟在0区域后面[cur, right]尚未处理的部分这是扫描的前沿区域(right, n-1]已经处理好的2全部归位在数组最后面。cur是当前扫描指针它从数组头部出发一路向右right从尾部出发向左移动left从左向右推进但它只负责标记0区域的右边界。四个区间合起来恰好覆盖整个数组不重不漏。整个过程就像把一条彩带从中间往两边捋左侧捋出来的0和1稳定归位右侧捋出来的2稳定归位中间不断缩短直到中间没有未处理的元素。这个区间划分是整道题的骨架也是后面所有代码和证明的基础。只要理解了left和cur之间的区域是“1区”、cur到right之间是“未处理区”这道题就成功了一半。2.2 遇到0、1、2时的三种动作当cur指向某个元素时分三种情况处理。第一种nums[cur] 0。这时候需要把这个0放到数组最前面的0区。做法是交换nums[left]和nums[cur]然后left向右移动一位cur也向右移动一位。为什么cur要跟着移动因为交换过来的元素必定是1或者0——left之前的区域已经处理过了left位置不可能是2如果有2早就被交换到right那边去了。既然是0或1它们属于已处理的范畴cur就可以放心往前走。第二种nums[cur] 1。1本来就该待在中间区域而中间区域恰好是[left, cur)这个区间所以什么都不用做cur直接往前移动一位即可。第三种nums[cur] 2。2应该被放到数组末尾的2区。做法是交换nums[cur]和nums[right]然后right向左移动一位。注意此时cur不能移动这是整道题最关键的地方下面单独拎出来说。这三个动作合起来就是整个算法全部的核心逻辑。别小看这三次分支判断它们的实现顺序和移动规则稍有差错结果就会完全不对。2.3 全篇关键交换2之后cur为什么不能动这里应该是全文最需要停下来思考的一行。很多人第一次写三指针时会在nums[cur] 2的分支里习惯性地补上cur然后发现某些用例排序结果是错的但换几个用例又对了百思不得其解。原因其实很简单从right指针交换过来的元素是“未处理区域”的它到底是0、1还是2谁也不知道。只要cur向右移动这个未知元素就被直接跳过了后面再无机会处理。用一个最小的反例就能说明白。数组[1, 2, 0]初始left0, cur0, right2。nums[0]1属于情况二cur变成1。第二轮cur1nums[1]2交换cur和right数组变成[1, 0, 2]right变成1。注意此时cur仍然指向索引1位置上的值是0。如果当初写了curcur会变成2循环条件cur right也就是2 1不成立循环直接结束输出[1, 0, 2]排序失败。问题正出在这里交换过来的0必须继续和left交换才能走到最前面一旦cur跳过就再没机会了。所以正确写法是cur保持不动让下一轮循环重新判断这个新元素。这不仅是代码层面的技巧更是维持“未处理区域不丢元素”这个不变量的关键。有一个细节在面试中非常加分如果你能在写完代码后主动补一句“交换2之后cur不能动因为交换过来的是未知元素需要下一轮判断”面试官通常能立刻确认你不是在背题。3. 代码落地两种实现与一套证明3.1 Python和C参考实现思路理清楚了代码其实很短。先给Python版本注释写得很详细方便照着敲def sort_colors(nums): left, cur, right 0, 0, len(nums) - 1 while cur right: if nums[cur] 0: nums[left], nums[cur] nums[cur], nums[left] left 1 cur 1 elif nums[cur] 1: cur 1 else: nums[cur], nums[right] nums[right], nums[cur] right - 1 # 注意cur不动交换过来的元素下一轮重新判断 return nums再给C版本笔试时更常见void sortColors(vectorint nums) { int left 0, cur 0, right nums.size() - 1; while (cur right) { if (nums[cur] 0) { swap(nums[left], nums[cur]); } else if (nums[cur] 1) { cur; } else { swap(nums[cur], nums[right--]); } } }两个版本逻辑完全相同区别只是语法。我更推荐你在本地把Python版跑通之后再手动翻译成C版本写一遍这比直接背代码有效得多。翻译的过程会逼你重新思考每一行代码的含义尤其是交换操作和指针移动的顺序。代码里最值得琢磨的是while循环的条件cur right。这个条件决定了“未处理区域”是[cur, right]只要cur超过right说明未处理区域已经空了整个数组自然有序。千万不要写成cur len(nums)否则right已经缩到左边去了cur还会继续往右扫描已经归位好的2区域不仅多干活还可能把排好的2区搞乱。3.2 循环不变量为什么这个算法永远不会错刷题的时候很多人喜欢“看懂了”就过但如果你想真正吃透这道题我建议花五分钟看一下循环不变量的证明。这个思维工具在面试时特别加分很多复杂问题只要能用不变量框住就能避免“总觉得对但说不清为什么对”的尴尬。我们断言每次while循环开始的时候以下四个区间分别成立——[0, left)内全是0[left, cur)内全是1[cur, right]内是未处理元素[right1, n)内全是2。四个区间不相交且并集是整个数组。初始时left0[0, 0)是空区间自然不会含错元素cur0[0, 0)也是空rightn-1[right1, n)是空[cur, right]正好是整个数组全部未处理。初始条件成立。假设某轮循环开始时四个区间满足条件。如果cur指向0交换left和cur之后left位置变成0left后[0, left)仍是纯0区cur位置变成原来的left位置的值要么0要么1不可能是2cur后[left, cur)仍是纯1区。其余区间不变不变量保持。如果cur指向1相当于把1归入了[left, cur)区间cur后不变量依然成立。如果cur指向2交换cur和right后right位置变成2right--后该位置落入(right, n-1]的2区cur位置变成原right位置的值是未处理元素留在[cur, right]中。不变量依然成立。终止时由于循环条件是cur right退出必然意味着cur right 1。此时[cur, right]为空未处理区域消失。四个区间收缩为三个[0, left)全是0[left, cur)全是1[cur, n)全是2。三块恰好覆盖整个数组排序完成。这段证明看起来有点形式化但实际价值很高。一方面你能用它说服自己和面试官另一方面当你以后遇到更复杂的数组分区题或快排优化题时这套“区间划分不变量”的思考方式可以直接迁移。3.3 边界用例演练把算法在纸上跑一遍光看代码和证明还不够我建议你在纸上把算法过程跑一遍。选一个有点代表性的用例[2, 0, 2, 1, 1, 0]。初始left0, cur0, right5数组为[2,0,2,1,1,0]。第1轮cur0nums[0]2和nums[5]交换 → [0,0,2,1,1,2]right4cur保持0。第2轮cur0nums[0]0和nums[0]交换自己换自己→ [0,0,2,1,1,2]left1cur1。第3轮cur1nums[1]0和nums[1]交换 → 数组不变left2cur2。第4轮cur2nums[2]2和nums[4]交换 → [0,0,1,1,2,2]right3cur保持2。第5轮cur2nums[2]1cur3。第6轮cur3nums[3]1cur4。此时cur4right3cur right循环结束。数组为[0,0,1,1,2,2]完美。留意第3轮nums[1]0left1所以是自己和自己交换数组看起来没变化但left和cur都推进了。这说明边界上的“自己换自己”是完全正常的不影响正确性。很多刚开始写的人看到交换前后数组没变会怀疑自己写错了其实没有这正是不变量在起作用。空数组[]left0, cur0, right-1cur right循环不进入返回空数组。单元素数组[0]cur0, right0等于0自己和left交换left1, cur1循环结束。全部一样的数组比如[2,2,2]也一样能正确归类——每次cur指向2交换后right递减cur保持0直到curright数组变成[2,2,2]没有变化。边界用例都能通过说明逻辑是鲁棒的。4. 举一反三从三色到K色的通用解法4.1 K种颜色的两种通用路线面试官可能不会满足于3种颜色他可能会问“如果数组里有k种颜色怎么办”这个问题非常有延展性值得提前准备。第一种路线是计数排序法适合k比较小的情况。第一遍遍历统计每种颜色出现的次数第二遍遍历按统计结果依次回写。时间O(nk)空间O(k)思路简单不易错。对于k3的情况这其实是比三指针更稳妥的兜底方案。第二种路线是递归三向切分。思路是把三指针方案“推广”到多色一次三向切分可以把选定的基准色全部归位把数组切成“小于基准色”“等于基准色”“大于基准色”三块然后对左右两块递归各自再选一个新基准色继续切分。这本质上就是快速排序的三向切分思想时间复杂度O(n log k)空间O(log k)递归栈开销。k比较小时它甚至比计数排序更省空间因为它不需要额外的计数器数组。实际场景里我更推荐你根据k的大小来判断k是常数级别比如3、4、5时直接计数排序或三指针都行k接近n时直接用普通快排或者堆排反而更优。这个判断思路在面试中很加分它体现了你不只是会背题还会根据数据特征选算法。4.2 颜色分类与快速排序三向切分的联系三指针方法绝不只是一道孤立的题。你把它往深处想一层它就是快速排序的三向切分partition的基础。经典的快速排序partition把数组分成“小于基准值”和“大于等于基准值”两块如果数组中相等的元素太多比如大量重复值二路partition会退化得很厉害。三向切分则把数组分成“小于基准值”“等于基准值”“大于基准值”三块对重复元素多的数组格外友好。你看看颜色分类的区间划分——0区、1区、2区——是不是和三向切分的“小、等、大”完全对应荷兰国旗问题被提出来恰恰就是为快速排序的三向切分做铺垫的。理解了颜色分类再去看快排的三向切分代码你会觉得非常顺畅基准值就相当于“颜色1”比它小的放左边比它大的放右边相等的留在中间。这道题练好了后面学快排优化、top-k问题、荷兰国旗类问题都能省不少力。其他和这道题共享“指针维护区间”思维的题目也不少移动零把0和非0分开、奇偶分离按奇偶分区、数组去重维护不重复区间等等。如果你能把三指针这套“给每个区间找边界指针”的方法吃透这些题目做起来会顺手很多。5. 面试考场常见错误与加分回答5.1 新手最容易犯的五个错误我在辅导和面试里看过太多人在颜色分类上翻车总结一下高频错误你写的时候对照检查。错误一交换2时顺手写了cur。这个问题在2.3已经重点讲过是错误率最高的一处。原因是“习惯性思维”——普通交换操作后该指针往前走但这里交换来的是未知元素必须原地再判一次。错误二循环条件写成while cur len(nums)。这样cur会把已经归位到右侧的2区域也扫描一遍。如果数组末尾的2比较多cur一旦越过right进入2区很可能把它们又交换出来越弄越乱。正确写法是while cur right。错误三交换0时指针移动顺序写反了。先left再cur或先cur再left其实没有本质区别——left和cur都递增交换顺序不会影响结果。但有些人会写成交换后只动left不动cur这就错了。从left交换过来的值不会大于1cur一定可以往前走。错误四忘记处理nums[cur] 1的情况。有些人在写完0和2的分支后觉得“剩下的就是1”就直接写else结果把2也归到1类。建议三个分支都显式写出来代码更长一点但不容易错。错误五把right初始化为len(nums)而不是len(nums)-1。right应该是最后一个元素的下标初始化成len(nums)会导致数组越界访问或者需要额外的判断。这类边界问题在笔试代码中很容易被卡住。我建议你把上面的错误和对应写法整理成一个检查表每次写完这题先过一遍表再提交。面试的时候哪怕你写错了主动说出“这里有个坑交换2之后cur不能动”面试官也通常会给你加分——能识别坑本身就说明你有实战经验。5.2 面试官追问的四个问题怎么答颜色分类的代码这么短面试官一般不会只让你写完代码就放你走追问的套路基本固定。追问一“为什么不用sort”回答要抓住复杂度sort是O(n log n)而这道题只需要O(n)因为只有三种值可用计数/分区并且sort无法展示对数据特征的利用能力。写代码时数据的信息量比通用算法更重要。追问二“能不能只用一个指针”不行。一个指针只能维护“当前访问位置”这一个信息无法同时维护0区域和2区域的边界。如果需要记录两个边界就需要两个额外指针。这个回答能体现你对“信息本质”的理解——每多一个需要维护的区间大概率就需要多一个指针。追问三“如果颜色不是数字0、1、2而是一些随机标签比如字符串怎么办”此题的三指针依赖数字的排序关系但对任意标签可以用一次遍历做“分三组”用等值比较即可不需要排序关系。先固定一个基准值把其他值分成“等于基准值”和“不等于基准值”两组要分成三组就需要两个基准值或两轮操作。总之核心在“分区”而不在“排序”标签类型不影响根本逻辑。追问四“如果要求稳定排序三指针方案还能用吗”不能直接沿用原版三指针因为交换操作会破坏相对顺序。稳定解法可以用两趟扫描计数排序回写时按原顺序扫描填充来保持稳定性或者用额外的稳定排序算法。这个答案能体现你对“稳定性”这个概念有认知而不仅仅是会背模板。我把这几个追问当成“价值点”来看。面试官问它们不是要难为你而是想确认你是真的理解解题思想还是在背题。所以平时练习时建议每道题都自问一遍为什么这样写复杂度是多少边界在哪有没有替代方案这套自我追问的习惯比多刷十道题还管用。写了这么长的拆解最后说点个人体会。颜色分类这道题我前前后后刷过不下十遍每次重刷都有新的理解。最深的感悟是刷算法题刷的其实是“你看问题的视角”。大多数人第一次看到这道题想到的是“怎么排序”而三指针方案教给你的是“怎么用区间去切一个数组”。这个视角一旦建立你会发现很多问题——移动零、快排分区、荷兰国旗、甚至二分查找的变体——底层都是同一套“用指针维护区间”的方法论。如果你现在觉得三指针有点绕不用急。第一次看不懂就对着代码把用例在纸上走一遍走完一遍再看一遍循环不变量然后合上代码自己默写一遍。这个过程我经历过大概三遍之后这道题就会像“if里面写三个分支”一样自然。真的吃透这道题你得到的远不止一道题的答案而是一整套关于“分区式思考”的底层能力。