Hot 100 系列里的第 75 题“颜色分类”是一道被很多人低估的经典数组题。题目给一个只包含 0、1、2 的数组让你原地排成 0 全在左、2 全在右、1 稳定在中间。不夸张地说这道题吃透了你在面试里遇到“原地分区”“三向切分”“双指针边界”相关的题目都能少踩一半的坑。这篇文章从题干拆解、思路演进、指针原理、代码实现到面试答法一次讲全新手能跟着学会老手也可以顺手查漏补缺。1. 题目到底在问什么1.1 题干与样例“颜色分类”的大意是给定一个包含红色、白色、蓝色共 n 个元素的数组原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。用整数表示的话0 代表红色1 代表白色2 代表蓝色。标准样例是 [2,0,2,1,1,0]排完变成 [0,0,1,1,2,2]。这句话信息量不小。首先“原地”意味着空间复杂度要尽量低不能搞一张大表存中间结果其次“相同颜色相邻”说明不是要你统计谁多谁少而是要调整数组内元素的位置最后进阶要求“一趟扫描”是真正的门槛几乎所有高质量讨论都围绕它展开。很多人写代码前根本没读全题目直接调排序等面试官追问“你能做到 O(n) 加常数空间吗”才发现问题。我复盘过自己做这道题时的状态第一次提交用的是内置排序代码长这样def sort_colors(nums): nums.sort()不到十行全部用例通过。但当时如果面试官多问一句“为什么这题要放进经典清单”我是答不上来的。这就是典型的“会调用工具不会分析问题”。1.2 先把复杂度基础对齐讨论这道题之前最好先统一一下复杂度概念。时间复杂度看的是基本操作次数随输入规模增长的趋势空间复杂度看的是额外内存占用。这里要强调“额外”两个字因为排序数组本身占用的空间不计入额外开销你开一个和原数组等大的辅助数组就要算 O(n)。颜色分类的独特之处在于它的最优解同时满足 O(n) 时间、O(1) 空间、一趟扫描三个条件。这三个条件单独拿出来都不算难但组合在一起就对数组操作提出了很高要求。很多人优先想到的计数排序能满足前两个却栽在“一趟扫描”上。理解这一点你才算真正看懂了题目要求也才能明白为什么这题不是考“排序”而是考“分区”。1.3 隐藏考点区间维护能力数组题最容易犯的毛病是只管“改值”不管“挪动”。比如你看到 nums[i] 2顺手把它赋成一个新值却忘了原本那个位置上的元素应该先去哪里。颜色分类逼着你同时维护多个指针并且每走一步都要清楚当前元素应该归到哪个区间。另一个隐藏考点是“稳定区间”的维护。排好序之后数组应该被分成三段左段全是 0中段全是 1右段全是 2。你永远不会知道某一次交换会不会破坏已经排好的区间所以必须用循环不变量来约束每一步操作。我的经验是做这类题时先在手边画出三段区域把 left、right、i 三个指针的含义写在注释里比直接埋头写代码靠谱得多。这道题也因此成了很多人第一次正式接触“循环不变量”概念的地方。2. 从暴力到优雅三条思路的演进2.1 方案一直接排序是热身课最简单的解法当然是用语言自带的排序函数对数组排序。Python 里是 sort()C 里是 std::sort。这个方案在功能上完全正确代码量和出错概率都是最低的两三行就能交卷。你可能会问那不直接这题就结束了如果只看“通过”确实够了但刷题和面试的评分标准从来不是只看出不出结果。直接排序有两个问题。第一个是复杂度比较排序的平均时间复杂度是 O(n log n)对于只有三种取值的数据完全没有利用任何结构信息。第二个是它把问题“外包”给了别人面试官看不到你自己对指针和分区的理解。所以我的建议是它只能作为热身和解法的对照基线不能作为最终方案。那是不是所有情况下内置排序都不好不是。实际工程项目里如果数组规模大、元素类型复杂直接调用经过深度优化的排序库往往是更正确的选择。面试题和工程实现本来就是两套评价标准讨论颜色分类时我们关心的是后者。2.2 方案二计数排序两遍扫描达标看到值域只有 0、1、2第一反应应该是计数排序。开一个长度为 3 的计数器数组第一遍遍历记录每种颜色出现的次数第二遍遍历按计数器把数组回写。代码可以写成这样def sort_colors(nums): cnt [0, 0, 0] for x in nums: cnt[x] 1 idx 0 for color in range(3): for _ in range(cnt[color]): nums[idx] color idx 1这个解法的时间复杂度是 O(n)空间上只用了固定长度的计数器所以也是 O(1)。它的优势是足够直观几乎不存在写错的可能。它的劣势也很明显遍历了两遍第一遍读数据统计次数第二遍写数据回填。如果你只是被要求“原地排序”计数排序完完全全合格如果你被追问“能不能一趟扫描”那就得继续往双指针走。面试时有个小技巧先大方地给出计数排序再主动补一句“如果必须只扫一遍可以用三指针”。这比直接甩出最优解更显沟通能力也让面试官知道你知道有更优路线。不要一上来就憋最优解除非你对自己的表达能力特别自信。2.3 方案三一趟扫描的吸引力一次遍历的核心思路是不再“先统计再回写”而是在扫描的过程中顺手把元素放对位置。具体来说用 left 指针维护下一个 0 该放的位置用 right 指针维护下一个 2 该放的位置用 i 扫描当前元素。扫描的过程中如果发现 0 就扔到左边发现 2 就扔到右边剩下的 1 自然停留在中间。这里最关键的一点是当把 2 交换到 right 位置时从 right 换回来的元素我们还没看过所以 i 不能前进而当把 0 交换到 left 位置时从 left 换回来的元素最多是 1而 1 正好是当前该跳过的值所以 i 可以放心前进。这个不对称性是整个算法最容易出 bug 的地方后面我会专门讲。三条思路摆在一起可以清楚看到一条优化路径先借助现成工具再挖掘数值特性最后把时间、空间、遍历次数都压到极限。面试官想听的就是这个演进过程而不是你直接跳到最优解。3. 核心算法荷兰国旗三指针方案3.1 指针含义与循环不变量荷兰国旗问题最早来源于计算机科学家对三色旗排序的描述把红、白、蓝三种颜色的旗子按顺序排好只能通过交换实现。这道颜色分类题就是它的数组版本。标准解法用三个指针left、right、i。很多人第一次学这题会被“三个指针”吓到其实它们的分工非常明确。三个指针的职责可以写成一段注释[0, left) 区间已经排好的 0全是红色[left, i) 区间已经扫描过且确定是 1 的部分全是白色(right, n-1] 区间已经排好的 2全是蓝色[i, right] 区间还未扫描的未知区域这个不变量是整个算法的灵魂。每一步交换都必须确保它始终成立。写代码前先在纸上把这个区间图画出来比任何技巧都管用。我见过不少人代码跑出来是错的但自己怎么都查不出就是因为脑子里没有这幅区间图走一步算一步。3.2 交换规则与不对称性当 i 小于等于 right 时循环持续进行。逐个取出 nums[i] 判断分三种情况如果 nums[i] 0说明这个元素应该放到最左边的 0 区。交换 nums[i] 和 nums[left]然后 left 和 i 都加一。为什么 i 可以加一因为从 left 换过来的是旧 left 位置的元素它要么是 1要么是因为之前所有 0 都已经处理完毕所以不可能是 0最多是 1而 1 正好处于中间区域i 可以直接跳过。如果 nums[i] 1什么都不用做i 加一。因为 1 就应该待在中间区当前元素已经在正确位置上了。如果 nums[i] 2交换 nums[i] 和 nums[right]right 减一i 不动。为什么 i 不动因为换过来的是 old right 位置的元素它可能是 0、1、2 中的任意一个必须再判断一次。很多人会纠结为什么同样都是交换一个 i 要动、一个 i 不动原因就是在交换之前你是否知道换回来的元素是什么。和 0 区交换时换回来的是确定已知的中间元素可以直接跳过和 2 区交换时换回来的是未知元素必须继续判断。理解了这个不对称性算法就掌握了一大半。3.3 完整走一遍样例拿 [2,0,2,1,1,0] 来走一遍。初始 left0right5i0。i0nums[0]2交换 nums[0] 和 nums[5]数组变成 [0,0,2,1,1,2]right4i 仍然为 0。i0nums[0]0交换 nums[0] 和 nums[0]数组不变left1i1。i1nums[1]0交换 nums[1] 和 nums[1]left2i2。i2nums[2]2交换 nums[2] 和 nums[4]数组变成 [0,0,1,1,2,2]right3i 不变。i2nums[2]1执行 ii3。此时 i3right3满足 i right继续判断。nums[3]1执行 ii4。i4 right3退出。最终数组 [0,0,1,1,2,2]。注意最后一步。当 i 和 right 相等时这个位置的元素仍然属于未知区必须处理。这解释了为什么循环条件是 i right而不是 i n 或者 i right。有些实现写 i right在某些输入下会在边界处留下未处理的元素。3.4 一个会踩坑的反例为了说明循环条件的重要性我们看一个用例[1,2,0]。如果你把循环条件写成 i nums.lengthwhile 循环会在 i2 时进入。此时 left0right1i2。nums[2]0swap(nums[left], nums[i])数组变成 [0,2,1]left1i3循环退出。但 right1 位置的 2 根本没有被处理最终输出 [0,2,1]明显是错的。问题出在哪因为 i 超过了 right但 right 还没有收敛到正确位置未知区实际上已经不存在了可 2 却被留在了中间区。我在本地反复验证过只要坚持 i right 这个条件同时在交换 2 时不移动 i就绝不会出现这种越界。很多讲这道题的文章只贴代码不解释这里导致读者抄下来能在样例上通过换个输入就翻车。4. 复杂度、理论源头与常见变体4.1 三种方案的复杂度对比这里用一张表把三种思路放在一起比较方案时间复杂度空间复杂度是否一趟扫描实现难度直接排序O(n log n)O(1)否极低计数排序O(n)O(1)否两遍低三指针O(n)O(1)是中这个对比在面试中是标准台词。三指针方案在时间上仍然是 O(n)因为每一步操作后要么 right 减一要么 left 加一要么 i 加一三个指针总体移动次数不超过 3n所以总操作仍然是线性量级。空间上只用了几个指针变量常数空间无疑。这里有个容易被忽略的点算法虽然是一趟扫描但交换次数可能接近 2n也就是说最坏情况下每个元素可能被交换两次。这不会改变 O(n) 的量级但如果你跟面试官聊到常数因子提前讲清楚会比被动被问好很多。4.2 荷兰国旗与三向切分快排这个三指针方案和快速排序里的三向切分几乎一模一样。经典快排在面对大量重复元素时会退化到 O(n^2)三向切分快排通过把数组分成“小于 pivot”“等于 pivot”“大于 pivot”三段来避免这个问题。颜色分类中的 0、1、2 就对应小于、等于、大于的概念而 pivot 恰好固定在 1。理解这一点之后你可以把颜色分类当作三向切分的一个特例pivot 已知是 1不用选数组里只有三种值所以也不需要递归。以后你学三向切分快排时再回头看这题会特别亲切。反过来如果你先掌握了颜色分类直接跳到三向切分的代码里也能很快认出那三个分区指针。4.3 常见变体颜色、奇偶、正负这题的变体非常多。最常见的是把“颜色”换成“奇偶”把奇数放左边、偶数放右边那是更简单的双指针问题。再比如“把所有 0 放前面、所有 1 放后面”的两色版本只需要 left 和 i 两个指针。还有“三路划分正数、负数、零”的问题本质上就是颜色分类换了个皮肤。链表版本的颜色分类也是一道高频题。通常有两种做法一种是把链表转成数组再排简单但额外占用空间另一种是用六个指针分别维护三条链表的头尾最后拼接。后者看着复杂但思路完全是区间思想的延续。如果你把数组版吃透链表版并不会太难主要是在操作节点指针时小心别丢节点。5. 代码实现、自测与面试答法5.1 一份可以直接抄的 Python 实现def sort_colors(nums): left, right, i 0, len(nums) - 1, 0 while i right: if nums[i] 0: nums[left], nums[i] nums[i], nums[left] left 1 i 1 elif nums[i] 1: i 1 else: nums[right], nums[i] nums[i], nums[right] right - 1 return nums这份代码的核心就是三根指针的移动规则。我习惯把 left 和 right 的命名写清楚因为它们分别代表 0 区和 2 区的边界而不是“左指针”“右指针”这种没信息量的名字。面试中即使先写伪代码也建议把区间不变量注释出来能显著降低后续调试时的心智负担。如果你用 C写法也差不多void sortColors(vectorint nums) { int left 0, right nums.size() - 1, i 0; while (i right) { if (nums[i] 0) { swap(nums[left], nums[i]); left; i; } else if (nums[i] 1) { i; } else { swap(nums[right], nums[i]); --right; } } }5.2 边界用例与随机验证自测时至少要把这几个用例跑一遍空数组、长度 1、全 0、全 1、全 2、已经有序、倒序、大量连续相同值、大量交替值。我最常用的是 [2,2,2,0,0,0]它能很快暴露循环退出条件写错的问题。另一个狠角色是 [0,2,1,2,0,1]它会同时触发三类交换走一遍基本心里就有底了。如果是在本地练手我还会写一个小脚本随机生成只含 0/1/2 的数组跑完三指针解法后和内置排序结果对比import random def check(): for _ in range(10000): n random.randint(0, 20) arr [random.randint(0, 2) for _ in range(n)] expected sorted(arr) sort_colors(arr) assert arr expected, (arr, expected)这个思路很笨但非常有效几次就能发现一些“恰好能过示例但在随机数据上崩掉”的写法。例如有些实现用 for i in range(n)遇到 2 交换后没有让 i 回到原地在特定输入下会跳过未处理的元素。跑随机测试是最快的检验方法。5.3 高频 bug 一览第一是把 right 的初始值写成 nums.length而不是 nums.length - 1导致数组越界。第二是在交换 2 时顺手对 i 自增把从右边换回来的值跳过了。第三是循环条件写成 i nums.length虽然很多数据能过但在某些情况下会把已经排到正确边界的元素当成未处理元素继续交换破坏结果。第四是交换 0 时忘记同时移动 left 和 i漏掉 left 会让 0 区扩张跟不上。这些 bug 大多源于对“换回来的值是否已知”理解不到位。我自己的调试习惯是在交换逻辑里临时打印 i、left、right 和整个数组重点看指针偏移是否符合区间定义。一旦发现 right 左边出现了 2 却不在正确位置基本就是 i 多走了一步或者循环多进了边界。这种排查思路放到任何数组分区问题上都能用。5.4 面试沟通建议面试时先不要急着写代码。可以这样说我注意到输入只有三种值如果只要求排序计数排序可以用两遍完成时间 O(n)、额外空间 O(1)如果要求一趟扫描可以用三指针把 0 和 2 分别交换到两端中间自然留下 1。然后画一下区间图再开始写。代码写完后主动用示例跑一遍并说明边界条件。面试官大概率会追问“为什么交换 2 的时候 i 不前进”这是核心考点能解释清楚基本就过关了。如果面试官再问“和快排的联系”能答出三向切分就是加分项。这里平时积累真的很重要临时想容易卡壳。6. 由这道题延伸出去的练习方法6.1 用一组题把指针思维练扎实我建议把这样一组题放进同一个学习周期移动零双指针的入门版移除元素锻炼“保留与跳过”的判断颜色分类三指针版三向切分快排的数组实现链表颜色分类。这几道题共用同一套大脑回路能帮你把“区间维护”这个模块快速练扎实。练习顺序也有讲究。先从两指针的移动零开始再到三指针的颜色分类最后挑战链表版本。每做完一道都回头看看上一道问自己这道题和上一道有什么区别多出来的那个指针到底在解决什么问题如果能答上来说明你真的在进步而不是只记住了代码模板。6.2 把指针思维迁移到其他场景指针思维不止用于数组排序。滑动窗口需要维护左闭右开区间链表题需要维护 prev、curr、nextN 数之和问题需要维护左右游标全都和这里的 left、right、i 有相通之处。每遇到一个区间或双指针问题都可以先画区间图再写代码长期积累下来正确率和速度都会有明显提升。我自己刷这道题的最大收获是养成了“先划分区域再写循环”的习惯。现在写任何带交换的数组题我都会在注释里把不变量写出来。这个习惯帮我避开了大量低级错误也让我在和人讲代码时逻辑更清楚。最后分享一个小技巧如果你在某一步拿不准应该移动哪个指针就回头读一遍自己写的循环不变量。0 区和 2 区的边界分别由 left 和 right 维护未知区由 i 和 right 圈定跟着区间定义走基本不会走歪。这个习惯我后来带到了所有双指针题目里收益远超这一道题本身。