“75.颜色分类”这道题在刷题圈里几乎无人不知——给一个只包含 0、1、2 的数组要求原地排序成 0 在前、1 居中、2 在后的形式。数字 0、1、2 抽象为颜色所以叫“颜色分类”。我第一次见它是在某刷题平台的热门题单里当时觉得这题简单到离谱这不是排个序就完事了吗直到面试官追问“能不能一次遍历搞定空间复杂度 O(1)”我才意识到这道题真正考的是双指针的边界控制以及背后那套荷兰国旗问题的 partition 思想。这篇博客我用自己踩过坑、刷了三遍才彻底想通的经历把这道题从暴力解到最优解拆开揉碎讲清楚包括三个指针各自负责什么、为什么遇到 2 交换后指针不能直接前进、边界条件到底怎么写才不容易错再看它在快速排序 partition、按条件切分数组这类场景里的延伸用法。无论你是刚开始刷题的新手还是准备面试想查漏补缺这篇文章应该都能让你少走点弯路。1. 题目的本质表面是排序底子是荷兰国旗问题1.1 为什么这道题值得反复刷这道题虽然只是一个中等难度的数组题但它把两个非常重要的算法思想浓缩在了十几行代码里一个是“不变量维护”另一个是“三向切分”。很多人在初学阶段把排序理解成调用 sort 函数或者在思考排序时只会冒泡、选择、插入这类比较排序。而颜色分类这道题完全没有用到任何比较大小之外的标准库排序它靠的是手动维护区间。我第一次刷的时候走了个弯路直接用桶计数统计 0、1、2 的个数然后重新填充数组。这种解法叫计数排序在这道题里其实是可行的因为数据范围只有 0、1、2 三种取值而且空间复杂度是 O(1) 的额外空间。但面试官通常不会满意因为他们真正想考察的是单次遍历原地解决的能力。这个能力背后的工具就是三指针也叫双指针的变体。为什么说这道题值得反复刷因为它卡得恰到好处代码量不大但每个指针的移动条件都是考点。你只要有一个地方想当然比如交换 2 之后顺手让当前指针前进测出来结果就乱套。它像是练习“边界思维”的绝佳素材能帮你建立一种条件反射——写循环之前先把循环不变量写清楚。1.2 从暴力解到双指针的思维跨越先说我最初想到的计数排序法写起来大概是这样先遍历一遍数组记录 0 出现了几次、1 出现了几次、2 出现了几次然后按照 0 的个数把开头都设成 0接着设成对应个数的 1最后设成 2。这个方案的时间复杂度是 O(n)空间复杂度 O(1)其实完全满足题目的基本要求。但问题是它遍历了两次而且它没有体现“排序过程”只是把统计数据回填。还有一种是直接调用语言内置排序比如 Python 的 sort()C 的 std::sort()也能过。但要是面试这种解法基本等于告诉面试官“我根本没想明白这题想考什么”。颜色分类这样的有限取值范围排序用比较排序去做属于杀鸡用牛刀还会把时间复杂度从 O(n) 拖到 O(n log n)。所以最优解的目标非常明确一次遍历、原地操作、不依赖额外数组、时间复杂度严格 O(n)。双指针解法处理这个需求的手法本质上是把数组划分成三个语义区域最左边全是 0最右边全是 2中间剩下的是还没扫描到的部分。维护这三个区域不需要额外的存储只需要记录三个边界位置然后通过交换元素来扩张区域。这就是荷兰国旗问题的解法也是三路快排的分区雏形。顺着这个思路去理解后面的代码实现就会非常自然。2. 三指针的核心思路拆解2.1 三个指针的分工谁负责扫谁负责守边界很多讲这道题的文章会把三个指针称为 low、mid、high或者 left、current、right名字不重要关键是要知道每个指针维护的是哪一段区间。我习惯把指针定义成这样left下一个 0 应该放的位置初始为 0它左边的元素全是 0。right下一个 2 应该放的位置初始为数组末尾它右边的元素全是 2。current当前扫描到的元素位置从 0 开始向右移动它负责遍历整个数组。在整个循环过程中数组始终满足这样的不变量区间 [0, left) 内全部是 0区间 [left, current) 内全部是 1区间 (right, n-1] 内全部是 2区间 [current, right] 是尚未处理的未知区域这个不变量是整个算法的灵魂。我一开始没有刻意去写不变量直接照着别人的代码敲结果一旦程序出错就完全不知道问题出在哪。后来我学乖了先在草稿纸上画一条数组线标出三个指针位置写上这四个区间的定义再去写循环体发现清晰非常多。你只要保证这个不变量在每一步交换后仍然成立算法就是正确的。2.2 循环终止条件为什么是 current right 而不是 current right这三个指针的相对位置决定循环什么时候结束。很多人容易把终止条件写成 current right这是比较常见的错误。当 current right 的时候最后一个元素其实还没有被扫描它处于 [current, right] 这个未处理区间内也就是说 current 指向的这个位置仍然需要判断一次。如果把条件写成 current right最后一个位置就被跳过了。我自己测试的时候遇到过这样的输入[2, 0, 1]。如果循环条件是 current right运行到 current 2、right 2 时会停下来但 nums[2] 是 1还没有被正确处理结果就错了。所以循环条件必须取等号保证每个元素都被处理到。再往深处想一下为什么循环结束时 current 会大于 right因为当 current 与 right 相遇后如果 current 指向的元素是 0 或者 1current 会向右移动结果 current 超过 right循环结束如果 current 指向的元素是 2交换后 right 左移current 会与 right 错开。不管哪种情况整个数组都会被三段区间覆盖完整顺序正确不变量成立。3. 完整代码实现与逐行讲解3.1 最直观的 Python 实现先给出我用着最顺手的实现语言是 Python。def sortColors(nums): left, current, right 0, 0, len(nums) - 1 while current right: if nums[current] 0: nums[left], nums[current] nums[current], nums[left] left 1 current 1 elif nums[current] 1: current 1 else: # nums[current] 2 nums[current], nums[right] nums[right], nums[current] right - 1这段代码里最核心的逻辑是三个分支当遇到 0 时把它交换到 left 指向的位置然后 left 和 current 同时前进。为什么 current 可以前进因为交换回来的元素也就是 nums[left] 原来的值只可能是 0 或 1。如果原来 left 位置是 0交换后 current 位置是 0它已经被处理过了如果原来 left 位置是 1交换后 current 位置是 1而 1 本来就该留在中间区域直接跳过即可。所以在这种情况下 current 前进是安全的。当遇到 1 时什么都不用做它已经在正确的位置区间内直接 current 1。当遇到 2 时把它交换到 right 位置然后 right - 1。这里 current 不能前进因为从 right 交换回来的元素可能是 0、1 或者 2完全是未知的。如果贸然前进这个未知元素就被跳过后续不会被处理。很多错误的写法就是少考虑了这一步我在 3.2 节会专门展开。3.2 最容易写错的两个细节第一个细节就是上面说的遇到 2 时交换之后不能顺手 current 1。我见过不少新手代码长这样else: # nums[current] 2 nums[current], nums[right] nums[right], nums[current] current 1 right - 1比如输入是 [2, 0, 1]第一步 current 指向 2交换后数组变成 [1, 0, 2]如果 current 前进到 1right 变成 1接下来 current 指向 0交换后变成 [0, 1, 2]看起来好像碰巧对了。但换成 [2, 0, 2, 1] 就会出错。所以正确做法是交换后只 right - 1让 current 停住下一轮继续处理交换回来的元素。第二个细节是交换的时候如果用中间变量 tmp 来写要注意先赋值哪一个。用 Python 的并行赋值还好但要换成 C 或 Java 写法顺序写反就会把 left 或 right 覆盖掉导致后面的操作全部错乱。建议这种交换逻辑统一用异或或者临时变量并养成先读后写的习惯。我再给一份 Java 版本给习惯用 Java 刷题的朋友参考public void sortColors(int[] nums) { int left 0, current 0, right nums.length - 1; while (current right) { if (nums[current] 0) { int temp nums[left]; nums[left] nums[current]; nums[current] temp; left; current; } else if (nums[current] 1) { current; } else { int temp nums[current]; nums[current] nums[right]; nums[right] temp; right--; } } }这份代码本质上和 Python 版本是同一个逻辑区别只在于手写交换。3.3 为什么时间复杂度是 O(n)、空间复杂度是 O(1)这道题的时间复杂度分析比普通排序更直白。整个算法只有一个 while 循环每执行一轮循环current 和 right 中至少有一个在朝着对方移动current 右移right 左移。遇到 2 的情况current 不动但 right 左移遇到 0 或 1 的情况current 右移。无论走哪个分支未被处理区间都在收缩因此循环最多执行 n 次左右时间复杂度是 O(n)。空间方面只用了 left、current、right 三个变量做指针交换操作就在原数组上完成没有申请额外数组所以额外空间是 O(1)。相比计数排序或者调用标准排序这套解法的优势不只是常数级别的时间快慢而是体现了一种非常强的设计意识用两个边界把数组切成三段就地整理。4. 常见问题与排查技巧实录4.1 死循环场景为什么有时候程序一直跑不完有一类错误是 while 循环里面遇到 2 交换后既没有 right - 1也没有 current 1代码会无限循环。比如写成这样else: nums[current], nums[right] nums[right], nums[current]交换后 right 没动current 也没动下一轮 current 还是指向同一个位置如果是 2 就再交换一次又回到原始状态变成死循环。排查这类问题其实有个非常有效的土方法把每一步交换后的数组打印出来。如果在连续几轮里数组状态完全没变化说明指针没有正确收缩。我调试这类指针题的习惯是写一个很小的辅助函数在循环里打日志打印出当前 left、current、right 和数组内容。看到数组不变就能立刻定位问题。等确认无误后再把日志删掉。4.2 边界测试用例这组数据让你一次测出所有隐蔽问题刷题时如果只测示例用例很容易带着错误提交后才被测试用例打脸。我用的一组测试用例包括空数组、只有一个元素、全 0、全 1、全 2、0 和 2 交替、2 和 1 混合、最长的两端都是边界值的情况。你把这组用例跑过基本能覆盖所有指针移动分支。test_cases [ [], [0], [1], [2], [0, 0, 0], [1, 1, 1], [2, 2, 2], [2, 0, 1], [1, 0, 2], [2, 2, 0, 0, 1, 1], [0, 1, 2, 0, 1, 2], [2, 1, 0, 2, 1, 0] ] for case in test_cases: sortColors(case) assert case sorted(case), ffailed: {case}上面的断言直接用 sorted 结果做对照虽然测试代码里用了排序但我们的算法本身并没有依赖排序库只是拿它做校验而已。刷题阶段这样写很合适。4.3 从错误提交中总结出的三条经验我在不同时间刷这道题时犯过三种错它们各有代表性。第一种是循环条件写成 current right具体影响前面已经分析过最后一个元素没有被处理。第二种是遇到 2 之后 current 1。这个问题在元素种类较多、重复较多时更容易暴露。第三种是交换 0 和 2 的时候把 right 和 left 写混。比如在 nums[current] 0 的分支里把元素交换到 right 而不是 left结果整个数组越整理越乱。这些错误的共同根源都是没有先在心里确认“当前这个位置的值到底是什么交换之后会变成什么值哪个指针可以移动”。建议你写代码之前养成一个习惯把每个分支中交换前和交换后的区间状态画出来不在脑内推理全貌就动手出错的概率极高。5. 从颜色分类到三路快排和真实工程场景5.1 快排 partition 的亲戚三路快排如果只看这道题本身你会觉得它就是一个灵活运用双指针的小题目。但把它放进整个算法知识体系里看它其实就是三路快排最核心的那个 partition 过程。经典快速排序的 partition 通常把数组分成小于基准和大于等于基准两部分也就是两路切分。当数组里存在大量重复元素时两路切分会导致重复元素频繁跨区交换性能下降。三路快排的解决办法是分成三个区小于基准、等于基准、大于基准。你看颜色分类里的 0、1、2完全可以替换成“小于基准的数、等于基准的数、大于基准的数”也就是说这题就是三路快排针对固定三个标签值的特例。我当时刷完这道题后专门去对照着实现了一版三路快排核心代码非常相似def quick_sort_3way(nums, lo, hi): if lo hi: return lt, i, gt lo, lo 1, hi pivot nums[lo] while i gt: if nums[i] pivot: nums[lt], nums[i] nums[i], nums[lt] lt 1 i 1 elif nums[i] pivot: nums[i], nums[gt] nums[gt], nums[i] gt - 1 else: i 1 quick_sort_3way(nums, lo, lt - 1) quick_sort_3way(nums, gt 1, hi)你发现没有这个 partition 内部的循环结构和颜色分类几乎是同一套模板只是把判断 0、1、2 改成了与基准值比较大小。理解了颜色分类三路快排的很多边界细节就顺带理解了。5.2 实际工作里的分类切分需求刷题时我们关心指针和边界但回到真实工程里这种按多个条件将数据切分成多个区间的操作也有非常广的应用场景。比如一段日志数据里有不同等级的消息你要把所有 error 放前面、warning 放中间、info 放后面并且不希望额外申请大量内存那就可以用类似三指针的思路原地整理再比如处理一批用户画像标签按“低中高”三档切分也可以直接套这套逻辑。不过实际开发中如果数据量不大或者关注代码可读性我一般不会真的写三指针原地修改而是更倾向于用 Python 的列表推导或者 sorted(key...) 来分组因为代码更直白。这道题的双指针解法更大的价值在于培养思维而不是让你在任何地方都用它替代标准库。懂得在什么场景用复杂算法、什么场景用标准库也是经验的一部分。5.3 面试延伸把颜色分类改一改你还认识它吗面试官非常喜欢在这道题基础上做变形目的是考察你理解了思想还是背了代码。常见的几个变体有把数组按照负数、0、正数分成三段保持各自相对顺序不确定只要求左负右正。把数组按照某个阈值分成小于、等于、大于三组这就是三路 partition 的朴素版。把奇数和偶数分成两段奇数在前偶数在后并且不改变它们之间的相对顺序这个就涉及稳定 partition比颜色分类更难。面对这些变形核心永远是先想清楚三个问题我的数组要被切成哪几段段与段的边界由什么指针维护每个分支里交换之后哪些指针可以移动、哪些不能移动。把这三个问题回答完代码基本就能正确写出来。我在面试辅导中见过不少同学能一口气把颜色分类的原题写对但一问到“如果改成偶数在前奇数在后你的代码哪里要改”就卡住了。原因是他们记住了代码的形态没有理解分区的本质。所以我建议刷完这道题后自己手动改一版负数/0/正数分类的代码再改一版奇偶分类的代码感受一下哪些逻辑需要调整哪些逻辑是不变的。这样才算真正吃透了它。最后说一点个人实操中的体会。我做这道题最大的收获不是记住了解法而是养成了一个习惯写任何涉及指针移动的循环之前先在注释里把四条区间边界写清楚。看起来是多花了几秒钟实际省下来的调试时间往往是几小时。颜色分类作为一道经典题教给你的不只是 0、1、2 怎么排更是一种组织代码边界的通用方法论。如果你现在还在靠背代码应付指针题我强烈建议你从这道题开始试试先画区间、再写逻辑跑一轮测试用例你会发现自己对“指针到底指向哪里”这件事的理解会上一个台阶。