“颜色分类”这四个字，只要你在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。初始时left=0，cur=0，right=n-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]：
- 初始left=0, cur=0, right=2。nums[0]=1，属于情况二，cur变成1。
- 第二轮cur=1，nums[1]=2，交换cur和right，数组变成[1, 0, 2]，right变成1。
- 注意此时cur仍然指向索引1，位置上的值是0。如果当初写了cur++，cur会变成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(vector<int>& 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]内是未处理元素；[right+1, n)内全是2。四个区间不相交，且并集是整个数组。
- 初始时left=0，[0, 0)是空区间，自然不会含错元素；cur=0，[0, 0)也是空；right=n-1，[right+1, n)是空；[cur, right]正好是整个数组，全部未处理。初始条件成立。
- 假设某轮循环开始时四个区间满足条件。如果cur指向0，交换left和cur之后，left位置变成0，left++后[0, left)仍是纯0区；cur位置变成原来的left位置的值（要么0要么1，不可能是2），cur++后[left, cur)仍是纯1区。其余区间不变，不变量保持。
- 如果cur指向1，相当于把1归入了[left, cur)区间，cur++后不变量依然成立。
- 如果cur指向2，交换cur和right后，right位置变成2，right--后该位置落入(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]。
初始：left=0, cur=0, right=5，数组为[2,0,2,1,1,0]。
- 第1轮：cur=0，nums[0]=2，和nums[5]交换 → [0,0,2,1,1,2]，right=4，cur保持0。
- 第2轮：cur=0，nums[0]=0，和nums[0]交换（自己换自己）→ [0,0,2,1,1,2]，left=1，cur=1。
- 第3轮：cur=1，nums[1]=0，和nums[1]交换 → 数组不变，left=2，cur=2。
- 第4轮：cur=2，nums[2]=2，和nums[4]交换 → [0,0,1,1,2,2]，right=3，cur保持2。
- 第5轮：cur=2，nums[2]=1，cur=3。
- 第6轮：cur=3，nums[3]=1，cur=4。
- 此时cur=4，right=3，cur > right，循环结束。数组为[0,0,1,1,2,2]，完美。
留意第3轮，nums[1]=0，left=1，所以是自己和自己交换，数组看起来没变化，但left和cur都推进了。这说明边界上的“自己换自己”是完全正常的，不影响正确性。很多刚开始写的人看到交换前后数组没变，会怀疑自己写错了，其实没有，这正是不变量在起作用。
空数组[]：left=0, cur=0, right=-1，cur > right，循环不进入，返回空数组。单元素数组[0]：cur=0, right=0，等于0，自己和left交换，left=1, cur=1，循环结束。全部一样的数组比如[2,2,2]也一样能正确归类——每次cur指向2，交换后right递减，cur保持0，直到cur>right，数组变成[2,2,2]没有变化。边界用例都能通过，说明逻辑是鲁棒的。
4. 举一反三：从三色到K色的通用解法
4.1 K种颜色的两种通用路线
面试官可能不会满足于3种颜色，他可能会问：“如果数组里有k种颜色，怎么办？”这个问题非常有延展性，值得提前准备。
第一种路线是计数排序法，适合k比较小的情况。第一遍遍历统计每种颜色出现的次数，第二遍遍历按统计结果依次回写。时间O(n+k)，空间O(k)，思路简单不易错。对于k=3的情况，这其实是比三指针更稳妥的兜底方案。
第二种路线是递归三向切分。思路是把三指针方案“推广”到多色：一次三向切分可以把选定的基准色全部归位，把数组切成“小于基准色”“等于基准色”“大于基准色”三块，然后对左右两块递归，各自再选一个新基准色继续切分。这本质上就是快速排序的三向切分思想，时间复杂度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交换过来的值不会大于1，cur一定可以往前走。
错误四：忘记处理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里面写三个分支”一样自然。真的吃透这道题，你得到的远不止一道题的答案，而是一整套关于“分区式思考”的底层能力。
与LALR：语法分析器的精度-代价权衡本质)
