重新刷到这道题的人多半会冒出同一个念头数组里只有 0、1、2 三个数字有什么好折腾的排序不就一行sort()的事吗但真正被面试官追问过就会明白题目最后那句“仅使用常数空间的一趟扫描算法”才是分水岭。热题100清单里的颜色分类表面上考的是排序实际考的是你对手指指针和计数分桶的底层理解。这篇文章我打算把两条主流路线都写透——计数法负责搭基线双指针负责上难度并给出可复现的代码、推导过程和我在实际调试中踩过的边界坑适合正在刷双指针专题的读者也适合面试前想把这题彻底吃透的人。1. 拿到题目别急着写代码三个隐藏约束决定了你的解法边界颜色分类不是一道复杂题但它非常能暴露解题前的思考习惯。很多人上来就写循环写到一半才发现排序是排好了却压根没有满足题目暗含的限制条件。所以我一般建议读题时先把约束条件画出来再决定用哪种策略。1.1 题面其实有两层大多数人都没读全这道题的描述通常有两层。第一层非常直白给你一个包含红色、白色、蓝色的数组用 0、1、2 分别代替这三种颜色请你原地排序使得相同颜色相邻并且按照 0、1、2 的顺序排列。到这里为止它就是最简单的“只有三类元素”的排序问题。第二层才是关键题目通常会追问一句“你能想出一个仅使用常数空间的一趟扫描算法吗”这一句直接把许多解法淘汰掉了。比如你开一个和原数组等长的临时数组把三类数字装进去再拷回来空间复杂度是 O(n)那就不合格再比如你写一个普通的两层循环冒泡或选择排序虽然原地但时间复杂度是 O(n²)在数据量一大时也不及格。我见过不少人在面试里卡在第二层。不是不会写代码而是根本没意识到“一趟扫描”这四个字意味着什么。读题的时候把这句话圈出来解题方向就清晰了一半。1.2 三个约束条件如何影响答案从思路上看这道题其实只有三个关键约束必须原地修改不能新建数组往回倒腾空间复杂度必须是常数级也就是不管 n 多大额外使用的内存不能随 n 增长最好能一次扫描完成而不是先遍历一遍统计、再遍历一遍回填。前两条把“复制粘贴”的方案去掉第三条把最朴素的“两次计数法”从“最优解”降级为“过渡解”。但要注意原题对“一趟扫描”的措辞是“你能想到吗”属于进阶挑战并不是说计数法提交不过而是面试评判时能写出一次扫描双指针的人显然理解更深。打个比方这就好比整理三种颜色的积木。计数法是把所有积木先按颜色数一遍然后再按数量重新摆回筐里动作本质上是两轮双指针法则要求你手里一次只碰一粒积木边看边决定放左、放中还是放右整个过程走完一遍就整理好。面试官真正想看的往往是后者。2. 计数法最容易写对也最容易被追问计数法是解决“取值种类有限”这类题目的万能起点。它的思路简单到不像算法题先开三个桶把 0、1、2 分别数清楚再按照数量回填到原数组里。2.1 思路和一次手动模拟拿[2, 0, 2, 1, 1, 0]举例。第一遍扫描数组数字 0 出现 2 次数字 1 出现 2 次数字 2 出现 2 次。于是回填结果就是两个 0、两个 1、两个 2[0, 0, 1, 1, 2, 2]。整个过程没有任何比较逻辑比任何排序算法都直观。2.2 计数法的代码与复杂度from typing import List def sort_colors_count(nums: List[int]) - None: cnt [0, 0, 0] for x in nums: cnt[x] 1 cur 0 for color in range(3): for _ in range(cnt[color]): nums[cur] color cur 1这段代码的时间复杂度是 O(n)因为两轮遍历加起来是 n 加 3空间复杂度是 O(1)因为计数器数组固定为 3 个元素不会随输入规模变化。很多人误以为“常数空间”等于“不能开数组”其实只要数组大小不随 n 变化就是常数空间。三个计数器完全合规。2.3 计数法的局限在哪里计数法的最大问题是扫描了两遍第一遍统计第二遍回填。对于原题这个数据范围它完全能通过但在面试场景里它更适合作为“保底答案”而不是“最终答案”。另外它有一个容易被忽略的扩展问题如果把 0、1、2 换成 k 种颜色计数器数组就需要开成 k 个空间复杂度变成 O(k)。当 k 很小比如三四种颜色这种做法依然高效但当 k 接近 n 时它的空间开销就不如通用排序了。所以计数法本质上是“利用值域范围小”的巧劲而不是通用排序手段。我在模拟面试里比较推荐的回答节奏是先给计数法承认它是两趟扫描然后立刻补一句“我还可以用双指针把它优化成一趟扫描”。这样既展示了基础能力又说明了优化方向比一上来就闷头写最优解更像一个会思考的工程师。3. 荷兰国旗双指针一次扫描把数组切成三段颜色分类的双指针解法在算法界有一个更经典的名字叫荷兰国旗问题。荷兰国旗恰好是红白蓝三色条状排列和这道题想表达的东西一模一样把数组切成三个连续的区间左侧全是 0中间全是 1右侧全是 2。3.1 三个指针的职责划分这个解法里维护三个指针p0指向下一个 0 应该放到的位置它左边的区域全部是 0p2指向下一个 2 应该放到的位置它右边的区域全部是 2i当前扫描的位置它和 p2 之间是尚未处理的区域。如果把数组比作一条传送带p0 和 p2 从两头圈出“待处理区”i 在待处理区里往前走。每遇到一个数字就把它丢到对应的区域同时收缩待处理区的范围。用一张表表示排序过程中的区域划分会更直观区间含义[0, p0 - 1]全部是 0[p0, i - 1]全部是 1[i, p2]尚未处理[p2 1, n - 1]全部是 2只要这个不变量成立循环结束时整个数组自然就是顺序排列的 0、1、2。3.2 核心代码from typing import List def sort_colors(nums: List[int]) - None: n len(nums) p0 0 p2 n - 1 i 0 while i p2: if nums[i] 0: nums[i], nums[p0] nums[p0], nums[i] p0 1 i 1 elif nums[i] 2: nums[i], nums[p2] nums[p2], nums[i] p2 - 1 else: i 1这段代码只有三种分支没有复杂嵌套真正需要动脑的地方在指针移动规则上尤其是遇到 2 的时候不能贸然让 i 前进这个细节我放在下一节专门讲。3.3 用 [2, 0, 2, 1, 1, 0] 手动跑一遍一步步追踪指针变化比单纯背代码更管用。初始p0 0p2 5i 0数组为[2, 0, 2, 1, 1, 0]。i0nums[0]2和 p2 交换数组变为[0, 0, 2, 1, 1, 2]p2 左移到 4i0nums[0]0和 p0 交换p0 右移到 1i 前进到 1i1nums[1]0和 p0 交换p0 右移到 2i 前进到 2i2nums[2]2和 p2 交换数组变为[0, 0, 1, 1, 2, 2]p2 左移到 3i2nums[2]1直接前进到 3i3nums[3]1直接前进到 4此时 i4p23i p2循环结束排序完成。到这里可以清晰看到每一轮循环要么让 i 向右推进要么让 p2 向左收缩整个过程确实只扫描了一遍。4. 交换、跳过与移动双指针循环的三条规则是这么定出来的双指针代码的难点从来不在“怎么交换”而在“为什么这里要动指针、那里不能动”。这节我把三条规则拆开推导一遍理解了之后你就不需要死记任何模板。4.1 遇到 0交换之后可以放心让 i 前进当nums[i] 0时执行的是和 p0 位置交换。p0 指向的是当前“0 区”的右边界这个位置上的旧值从哪来由于循环过程中 p0 始终不越过 i所以 p0 位置一定位于已经处理过的区间里它只可能是 0 或 1不可能是 2。交换之后当前 i 位置上要么是 1要么是 0。如果是 1它正好应该待在中间区直接前进没问题如果是 0那说明刚才和中区的某个 0 做了交换这个 0 也已经到了该在的位置。两种情况都不需要再检查一次所以 i 可以安全地加 1。4.2 遇到 2交换之后绝不能立刻 i这是整道题最容易翻车的地方。当nums[i] 2时从 p2 位置换过来的数字是未知的可能是 0可能是 1也可能是另一个 2。如果交换后直接让 i 前进换过来的这个新数字就会被跳过永远不会被处理。看一个反例就能明白。假设数组是[1, 2, 0]p00p22i1。按错误写法nums[1]2和 p22 交换数组变为[1, 0, 2]p2 变成 1错误写法此时让 i 变成 2直接跳出循环最终结果是[1, 0, 2]中间那个 0 根本没被处理。正确写法里交换后 p2 左移但 i 保持不动下一轮循环会重新检查换回来的数字 0并把它和 p0 交换最终得到[0, 1, 2]。4.3 循环结束条件为什么是 while i p2 而不是 i p2许多人写循环时习惯用但这里必须用。因为当 i 等于 p2 时待处理区域其实还有一个元素没有检查循环必须再执行一轮。最典型的情况是数组末尾是一个 2比如[2, 0, 1]i0p22nums[0]2交换后数组为[1, 0, 2]p21如果循环条件是 i p2i0 1继续i1nums[1]0和 p0 交换数组为[0, 1, 2]p01i2此时 i p2 为 false2 1退出结果正确但纯属巧合。换一个输入[0, 2, 1]条件 i p2 同样能碰巧通过。但如果是[1, 2, 0]这类组合错误立刻暴露。才是严格覆盖所有情况的写法因为只有当待处理区间完全为空也就是 i 超过 p2 时才能确定所有元素都归位了。用一个规则表总结指针移动逻辑当前位置的值操作i 是否前进原因0与 p0 交换p0 右移前进换回来的是已处理区间的 0 或 11不交换前进本来就属于中间区2与 p2 交换p2 左移不前进换回来的值未知必须重新判断5. 实测排雷边界用例、死循环和调试验证代码逻辑讲完之后最值得聊的就是实际提交时会踩的坑。我复盘自己过往刷题和帮人 review 代码的经历发现颜色分类的错误高度集中在几个固定位置。5.1 最容易写错的一行交换 2 之后顺手让 i很多人不是不知道“换回来的值需要再看一次”但写代码时手一快就加上i 1。这个错误在大多数测试用例里都不会立刻暴露因为很多输入恰好交换回来的是 1不影响最终结果。但面试官一旦构造一个[2, 0, 1]这样的用例立刻就能看穿。解决这个问题最好的办法不是靠记忆而是靠逻辑交换的本质是“把一个未知元素接过来处理”既然未知就必须在下一轮循环里重新面对它。只要这句话还在脑子里手就不会快。5.2 空数组和全相同元素的情况空数组时p2 n - 1 -1循环条件 i p2 一开始就不满足所以代码安然退出。但要注意如果某些实现里先访问nums[p2]而不是先判断循环条件空数组就会越界。全 0 场景下p0 和 i 同步右移交换是自己和自己做没有任何副作用全 2 场景下p2 不断左移交换也是自己和自己循环次数等于数组长度全 1 场景则只是 i 一路向前。这三种极端用例都可以用来验证代码没有数组越界和死循环。5.3 一张边界用例自检表刷题阶段我建议把下面这些用例跑一遍比随机测试更有效输入期望输出值得关注的点[][]空数组不能越界[2][2]单元素p2 和 i 重合[0][0]单元素p0 和 i 重合[2, 0, 1][0, 1, 2]交换 2 后跳过 0 的经典反例[1, 2, 0][0, 1, 2]同上验证 i 不动逻辑[0, 2, 1][0, 1, 2]混合场景[0, 0, 0][0, 0, 0]自交换场景[2, 2, 2][2, 2, 2]p2 快速左移[0, 1, 2][0, 1, 2]已经有序的场景[2, 1, 0][0, 1, 2]完全逆序场景我用这组用例做过多次验证它们几乎覆盖了双指针解法的所有分支组合。5.4 调试技巧打印三指针定位比脑子猜快得多如果代码跑错了不建议光盯着代码发呆加一行日志是最快的排查手段。在 while 循环体开头打印当前状态while i p2: print(fi{i}, p0{p0}, p2{p2}, nums{nums}) # 原有逻辑...打印出来的指针变化会直接告诉你问题出在哪一步。比如某个用例里交换 2 之后 p2 变了但 i 没变说明代码正确如果日志显示 i 越过了某个 0那八成就是“i 加早了”。写完正确答案之后也可以用临时断言做随机测试比如生成大量只含 0、1、2 的随机数组提交前跑一遍assert result sorted(result)能快速排除笔误。不过正式提交前记得把这些调试语句删干净LeetCode 的判题环境对多余的输出会比较敏感。6. 从颜色分类到三路快排把这题的指纹记在脑子里单独刷一道题价值有限把一道题和一个更广的算法家族联系起来价值才会放大。颜色分类看起来只是个小题但它正好是三路快排分区的雏形。6.1 三路快排的师徒关系快速排序有一个变体叫三路快排核心操作是选定一个基准值 pivot把数组分成小于 pivot、等于 pivot、大于 pivot 三个区域。颜色分类里如果默认基准值是 1那么小于部分是 0等于部分是 1大于部分是 2。也就是说颜色分类的三指针代码几乎就是三路快排里 partition 逻辑的简化版。很多人在理解三路快排时觉得指针很绕但如果先啃透颜色分类再去看三路快排的 partition就会发现代码结构非常相似区别只是把固定的 0、1、2 换成了动态 pivot并且递归应用到左右两侧。6.2 同类变形的识别信号遇到下面这些信号可以第一时间联想到颜色分类的思路数据只有两三种固定取值比如只有 a、b、c 三种状态的数据需要分组要求原地排序且空间复杂度必须常数级问题本质上是在“分成三类”而不是在“比较大小”。比如把偶数放在数组左侧、奇数放在右侧这就是一个两色版本可以用双指针一次遍历再比如某个文件列表需要按三种固定优先级重新排列同样可以用这个思路。模式识别能力就是在这种平凡题目里练出来的。6.3 面试表达顺序的建议最后聊一个小建议关于怎么回答才算完整。推荐顺序是先确认题意和约束明确“原地”“常数空间”“尽量一趟扫描”三个关键点给出计数法作为基线方案分析时间和空间复杂度承认它需要两趟扫描给出三指针双指针方案说明它如何把复杂度压到一趟扫描 常数空间手动模拟一个用例重点解释“遇到 2 交换后 i 不前进”的原因顺带说几个边界用例比如空数组、全 2、[2, 0, 1]。这个顺序的好处是层层递进面试官能看出你有意识地进行方案取舍而不是背答案。颜色分类这道题真正难的不是代码本身而是指针边界条件为什么这么定。只要把“换回来的值不确定就必须重新检查”这一条贯穿到所有双指针题目里你会发现很多看似不同的题底层逻辑其实都是同一棵树长出来的枝丫。这也是我想把这题拆开写透的原因。