企业官网建设流程全解析

重新刷到这道题的人，多半会冒出同一个念头：数组里只有 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 应该放到的位置，它左边的区域全部是 0；
• p2：指向下一个 2 应该放到的位置，它右边的区域全部是 2；
• i：当前扫描的位置，它和 p2 之间是尚未处理的区域。

如果把数组比作一条传送带，p0 和 p2 从两头圈出“待处理区”，i 在待处理区里往前走。每遇到一个数字，就把它丢到对应的区域，同时收缩待处理区的范围。

用一张表表示排序过程中的区域划分会更直观：

只要这个不变量成立，循环结束时，整个数组自然就是顺序排列的 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 = 0，p2 = 5，i = 0，数组为[2, 0, 2, 1, 1, 0]。

• i=0，nums[0]=2：和 p2 交换，数组变为[0, 0, 2, 1, 1, 2]，p2 左移到 4；
• i=0，nums[0]=0：和 p0 交换，p0 右移到 1，i 前进到 1；
• i=1，nums[1]=0：和 p0 交换，p0 右移到 2，i 前进到 2；
• i=2，nums[2]=2：和 p2 交换，数组变为[0, 0, 1, 1, 2, 2]，p2 左移到 3；
• i=2，nums[2]=1：直接前进到 3；
• i=3，nums[3]=1：直接前进到 4；
• 此时 i=4，p2=3，i > 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]，p0=0，p2=2，i=1。按错误写法：

• nums[1]=2，和 p2=2 交换，数组变为[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]：

• i=0，p2=2，nums[0]=2，交换后数组为[1, 0, 2]，p2=1；
• 如果循环条件是 i < p2，i=0 < 1，继续；
• i=1，nums[1]=0，和 p0 交换，数组为[0, 1, 2]，p0=1，i=2；
• 此时 i < p2 为 false（2 < 1），退出，结果正确，但纯属巧合。

换一个输入[0, 2, 1]，条件 i < p2 同样能碰巧通过。但如果是[1, 2, 0]这类组合，错误立刻暴露。<=才是严格覆盖所有情况的写法，因为只有当待处理区间完全为空，也就是 i 超过 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 一张边界用例自检表

刷题阶段我建议把下面这些用例跑一遍，比随机测试更有效：

我用这组用例做过多次验证，它们几乎覆盖了双指针解法的所有分支组合。

5.4 调试技巧：打印三指针，定位比脑子猜快得多

如果代码跑错了，不建议光盯着代码发呆，加一行日志是最快的排查手段。在 while 循环体开头打印当前状态：

while i <= p2: print(f"i={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 面试表达顺序的建议

最后聊一个小建议，关于怎么回答才算完整。推荐顺序是：

1. 先确认题意和约束，明确“原地”“常数空间”“尽量一趟扫描”三个关键点；
2. 给出计数法作为基线方案，分析时间和空间复杂度，承认它需要两趟扫描；
3. 给出三指针双指针方案，说明它如何把复杂度压到一趟扫描 + 常数空间；
4. 手动模拟一个用例，重点解释“遇到 2 交换后 i 不前进”的原因；
5. 顺带说几个边界用例，比如空数组、全 2、[2, 0, 1]。

这个顺序的好处是层层递进，面试官能看出你有意识地进行方案取舍，而不是背答案。

颜色分类这道题，真正难的不是代码本身，而是指针边界条件为什么这么定。只要把“换回来的值不确定，就必须重新检查”这一条贯穿到所有双指针题目里，你会发现很多看似不同的题，底层逻辑其实都是同一棵树长出来的枝丫。这也是我想把这题拆开写透的原因。