企业官网建设流程全解析

面试刷题列表里，`LeetCode热题100（颜色分类）》这道题几乎是绕不开的存在。第一眼看上去就是个“把 0、1、2 排好序”的简单数组题，很多人三分钟就能写出计数排序，然后觉得已经结束了。但真正被面试官追问时才意识到，这道题考察的是你能不能在不借助额外数组、只扫描一遍的情况下，用几个指针把数组归位。别看它题目短，里面埋着 partition 的思想、指针不变量的管理、边界条件的处理，几乎是高频题里的“性价比之王”。这篇就把我复习这道题的完整思路、代码细节和踩坑记录原原本本理一遍，给准备算法面试的朋友和刷题遇到瓶颈的同学做个参考。

1. 题目拆解与面试考察点

1.1 原题描述与输入输出

题目本身非常简短：给定一个包含红色、白色、蓝色，一共 n 个元素的数组，对它们进行原地排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。这里用整数 0、1、2 分别表示红色、白色、蓝色。

一个标准的示例是这样：

• 输入：nums = [2,0,2,1,1,0]
• 输出：[0,0,1,1,2,2]

要求里明确说了两件事：不能使用库函数sort，并且只能在原数组上操作。也就是说，我们不能图省事调一个Arrays.sort，也不能新建一个数组把结果装进去再复制回来。

这里有个容易忽略的地方：数组元素虽然只有 0、1、2 三种取值，但数组长度可能很大，比如 10 的 5 次方甚至更多。这意味着算法必须在线性时间内完成，空间上最好是常量级。这个约束看着简单，实际已经把很多“常规排序思路”卡掉了。

1.2 面试官真正想考什么

我在准备这道题的时候，一度以为“能写出正确答案”就够了。后来和一位朋友做模拟面试，他在五分钟内写出了计数排序，我问他“如果面试官要求你只遍历一遍数组呢？”他才意识到自己漏掉了一层。

这道题放在热题 100 里，并不是为了考你会不会“排序”，而是为了考你对数组指针的控制能力。具体来说，面试官想看这几件事：

第一，你能不能识别出“只有三种取值”这个特殊条件，从而放弃通用排序算法，想到用计数、分区这类线性做法。第二，你能不能在不新建数组的前提下，通过交换元素完成原地排序。第三，你能不能设计出只扫描一遍的算法，并且把每个指针移动的时机说清楚。最后，边界条件会不会漏，比如数组全为 0、全是 2、或者长度为 1。

这些能力在真实项目中同样重要。比如处理日志级别、状态机流转、将一组任务按优先级重新分组，都和这种“用一个指针维护边界”的思想相关。所以这道题不是在整花活，它背后是很实用的 partition 技巧。

2. 从暴力到优雅：三种解法的演进

2.1 最直观的计数排序解法

提到只有 0、1、2 三种值，很多人的第一反应是：遍历一遍统计三个数字出现的次数，再按顺序把数组重写一遍。这确实是最容易想到的解法，代码也短。

def sort_colors(nums): counts = [0] * 3 for num in nums: counts[num] += 1 idx = 0 for color in range(3): for _ in range(counts[color]): nums[idx] = color idx += 1

这个方法的时间复杂度是 O(n)，因为遍历数组统计需要 O(n)，重写数组也需要 O(n)，合在一起还是 O(n)。额外空间是counts这个长度为 3 的数组，严格说是 O(1)，因为不管数组多大，计数器只有三个。

所以在“空间复杂度 O(1)、时间复杂度 O(n)”这两个硬性指标上，计数排序其实是合规的。但它有一个特性：它对数组进行了两次遍历。第一次用于统计，第二次用于重写。

如果你够敏锐，会发现一个可以继续优化的点：既然元素只有三类，我们是否能在一次遍历的过程中，同时完成“把 0 挪到最左边、把 2 挪到最右边”这件事？这就是双指针和三指针解法的出发点。我在实际面试场景中通常建议先把计数排序讲出来，因为它容易被验证，代码风险低，可以作为保底方案。如果面试官追问“能不能只遍历一次”，再引出下面的解法。

2.2 双指针交换法（两趟版）

先聊一个过渡方案：用两个指针，一趟把 0 全部放到前面，另一趟把 2 全部放到后面。因为数组只有三种值，把 0 和 2 都处理好之后，中间剩下来的自然就是 1。

def sort_colors(nums): left = 0 for i in range(len(nums)): if nums[i] == 0: nums[i], nums[left] = nums[left], nums[i] left += 1 right = len(nums) - 1 for i in range(len(nums) - 1, -1, -1): if nums[i] == 2: nums[i], nums[right] = nums[right], nums[i] right -= 1

这个解法的正确性很好理解：第一趟从左往右扫，只要碰到 0，就和 left 位置交换，并把 left 往后移。这保证 left 左边的元素全部是 0。第二趟从右往左扫，碰到 2 就和 right 位置交换，保证 right 右边的元素全部是 2。中间剩下的必然是 1。

它仍然是 O(n) 时间、O(1) 额外空间，但比计数排序更进一步，因为它是通过交换来原地修改的，没有再“重写数组”。不过它的问题也很明显：需要扫描两遍。在某些场景下，两趟并不是大问题，因为常数倍的时间复杂度依然是 O(n)，但是很多面试官会继续追问：能不能一趟完成？

这个追问其实就是在导向接下来要说的三指针解法。

2.3 三指针荷兰国旗算法

颜色分类这道题之所以被很多人记住，是因为它是经典的“荷兰国旗问题”。荷兰国旗由三条色带组成，而我们的数组恰好也只有三种颜色，所以可以把数组分成三段：左边是 0，中间是 1，右边是 2。

三指针解法的核心是维护三个区域：

• 区间[0, p0)：全部是 0
• 区间[p0, curr)：全部是 1
• 区间(p2, n-1]：全部是 2
• 区间[curr, p2]：待处理区域

我们用一个当前指针curr从左往右扫描，用p0维护“0 区域的右边界”，用p2维护“2 区域的左边界”。初始时p0 = 0，curr = 0，p2 = n - 1。

循环不变量是：只要curr <= p2，就继续处理。遇到nums[curr]分三种情况：

• 等于 0：和nums[p0]交换，然后p0++，curr++
• 等于 1：不做交换，直接curr++
• 等于 2：和nums[p2]交换，然后p2--，但curr不动

这种做法的精妙之处在于，所有元素最多被访问一次，交换只发生在数组内部，所以时间和空间都极其高效。

3. 为什么荷兰国旗算法是本题的最优解

3.1 复杂度分析的一个误区

很多人看到“排序”两个字，第一反应是快排或归并，默认时间复杂度 O(n log n)。但这道题的约束是元素只有 0、1、2 三种值，普通比较排序的“信息论下界”并不适用。我们可以利用取值种类有限这个特性，把复杂度压到 O(n)。

荷兰国旗算法一次扫描完成排序，每个元素最多参与一次交换。curr只会从 0 走到p2，而p2只可能向左移动，所以整体操作次数是线性的。空间上只有三个变量，是真正的 O(1) 额外空间。

这里要强调一个容易被忽视的误区：有些同学认为“计数排序已经 O(n) 了，为什么还要费劲写三指针”。答案是：从复杂度的数量级上看，两者确实都是 O(n)，但常数项和“是否原地”不同。计数排序虽然也是常量级辅助空间，但它的第二次遍历是在“重写”数组，不是“交换”。如果你把一个数组元素理解成不可覆盖的对象，那么计数排序就需要额外考虑“能否安全覆写”的问题；而交换法不会丢掉任何信息。

另外，在一些面试场景中，“只扫描一遍”不仅仅是为了炫技，它代表一种思维习惯。真实项目里数据可能来自实时流，我们无法把数据全部缓存下来统计再重写，只能边读边调整。这时候一次遍历能做多少事，直接决定了方案的可行性。

3.2 原地算法与稳定性

原地算法的意思是，除了输入数组本身，我们只使用常数级别的额外空间。荷兰国旗算法的交换操作完全在原数组上进行，符合“原地”要求。

有一个细节值得想清楚：这个算法是不是稳定的？答案是否定的。因为在进行连续多次交换后，相同值的元素相对顺序可能被打乱。比如两个 1 分布在不同的位置，它们可能永远不会相互交换，但 1 与 0、2 交换时，1 的原始次序可能会变化。

那为什么题目不要求稳定？因为题目元素本身只是整数 0、1、2，相等的数字无法区分，稳定性没有意义。但如果把题目改造成“按优先级排序对象”，稳定性就可能变得重要了。我见过一个改造：数组里存储的是对象，每个对象有一个 color 字段，希望排序后相同 color 的对象还能保持原来的相对顺序。这个时候荷兰国旗算法就不适用，得换用归并排序或稳定计数排序的思路。

所以在面试时，如果面试官问“这个算法稳定吗”，不要只说“不稳定”，还要补充一句“本题中相等的数字没有区分价值，所以不稳定不影响结果；但如果对象还有其他属性，需要重新评估”。

4. 手写代码的边界处理与细节

4.1 核心代码实现（Python 与 C++）

先给出最经典的 Python 实现：

def sort_colors(nums): p0, curr, p2 = 0, 0, len(nums) - 1 while curr <= p2: if nums[curr] == 0: nums[p0], nums[curr] = nums[curr], nums[p0] p0 += 1 curr += 1 elif nums[curr] == 2: nums[p2], nums[curr] = nums[curr], nums[p2] p2 -= 1 else: curr += 1

这个写法里最容易记错的地方是：遇到 2 交换之后curr不要自增。原因很简单：从p2位置换过来的元素我们还没看过，它可能是 0、1、2 中的任意一个。如果直接curr++，就可能跳过一个还没处理的 0 或 2，导致排序结果错误。

同理，遇到 0 交换之后curr可以自增，这背后的理由需要多花一点时间理解。因为在循环进行过程中，p0和curr之间的区域全部是 1，所以p0位置的值也一定是 1。当nums[curr] == 0时，把nums[p0]这个 1 换过来，curr新位置上是 1，不需要再处理，所以可以直接前进。

C++ 版本也不复杂：

void sortColors(vector<int>& nums) { int p0 = 0, curr = 0, p2 = nums.size() - 1; while (curr <= p2) { if (nums[curr] == 0) { swap(nums[p0], nums[curr]); p0++; curr++; } else if (nums[curr] == 2) { swap(nums[p2], nums[curr]); p2--; } else { curr++; } } }

注意在 C++ 里，我故意把swap和指针自增分成了两行。有些简洁写法会写成swap(nums[p0++], nums[curr++])，虽然很多编译器能正常处理，但在参数求值顺序上容易引起争议，也降低可读性。面试手写代码时，清晰比“一行写完”更重要。

4.2 常见的指针移动陷阱

三指针算法的代码量很少，但指针移动的逻辑很容易错。我总结了一个口诀：遇到 0 交换后大步走，遇到 1 原地走，遇到 2 交换后回头等。

这里的“回头等”就是指curr不前进，因为要把换过来的元素重新判断一遍。很多人死记硬背“遇到 2 交换后不移动 curr”，却没有理解为什么，结果一到数组长度只有 2 时就开始乱。

举个例子：nums = [2, 0, 1]。

• 初始：p0=0，curr=0，p2=2
• 第 1 步：nums[0] = 2，交换 nums[0] 和 nums[2]，数组变为 [1, 0, 2]，p2=1，curr 仍为 0
• 第 2 步：nums[0] = 1，curr 变为 1
• 第 3 步：nums[1] = 0，交换 nums[0] 和 nums[1]，数组变为 [0, 1, 2]，p0=1，curr=2
• 循环结束，排序正确

如果第二步“遇到 2 后让 curr 前进”，数组会变成什么样？交换后 curr=1，然后 nums[1] = 0，交换 nums[1] 和 nums[0]，结果还是 [0, 1, 2]。看起来碰巧也能对，但换一个例子[2, 0, 2, 1, 1, 0]，错误就会暴露出来。因此最好还是严格按照不变量来分析。

另一个陷阱是循环终止条件。有些同学会写while (curr < nums.length)，这会导致访问越过p2，把已经排到右边的 2 又拿回来处理，出现死循环或错误交换。必须写成while (curr <= p2)，因为当curr超过p2时，待处理区间已经空了。

5. 常见错误与调试实录

5.1 死循环与跳过元素的现场

有一次我帮模拟面试的 A 同学调试这道题，他写的代码在遇到一连串 2 的时候会直接爆掉。他的版本是这样的：

def sort_colors(nums): p0, curr, p2 = 0, 0, len(nums) - 1 while curr <= p2: if nums[curr] == 0: nums[p0], nums[curr] = nums[curr], nums[p0] p0 += 1 curr += 1 elif nums[curr] == 2: nums[p2], nums[curr] = nums[curr], nums[p2] p2 -= 1 curr += 1 # 错误点 else: curr += 1

他加了curr += 1，然后对[2, 0, 2, 1, 1, 0]手动模拟到第 4 步，发现结果变成[0, 1, 1, 0, 2, 2]，中间混进了一个 0。问题就出在：当nums[curr]是 2 时，从右边换过来的元素可能是 0，需要继续检查，如果直接跳过它，就会有 0 留在中间区域。

调试这类问题最好的方式不是打印日志，而是在纸上模拟一个长度 6 的数组，把p0、curr、p2三个指针标出来，每执行一次交换就更新一次。模拟两遍之后，你会对“为什么curr不动”产生直觉。

5.2 边界条件排查速查表

我把容易出错的测试场景整理成了一个速查表，每次写完代码都会对着过一遍：

其中[2,1,0]这个用例特别能检验代码。初始时 curr 指向 0，数字是 2，需要不断把 2 换到末尾，然后等下一个位置的数字。如果curr过早前进，整个数组会变得很混乱。

5.3 使用计数排序时的隐蔽问题

很多人在写计数排序时反而会踩一个隐蔽的坑：重写数组时的索引更新方式。常见写法如下：

def sort_colors(nums): c0 = c1 = c2 = 0 for num in nums: if num == 0: c0 += 1 elif num == 1: c1 += 1 else: c2 += 1 nums[:c0] = [0] * c0 nums[c0:c0 + c1] = [1] * c1 nums[c0 + c1:] = [2] * c2

利用 Python 的切片赋值，看起来简洁，但它会创建新的临时列表，和“原地操作”的精神有所偏离。如果面试环境允许切片，这当然没问题，但如果面试官强调“就地”，最好用循环赋值，或直接展示三指针写法。另外，切片赋值的边界容易算错，比如在nums[c0:c0 + c1]里，很多人会把 c1 误写成 c2，导致结果错误。

其实计数排序还有一种原地双指针写法：先扫描一遍统计个数，然后用idx顺序填充。这个写法不需要创建临时列表，也更符合“原地”的精神。但不管怎么写，计数排序始终需要两趟扫描，这是它的结构性特征。

6. 面试现场指南与后续扩展

6.1 如何在面试中展示思路

这道题在面试中的最佳展开节奏，我认为是“分层递进”。

拿到题之后，不要急着写代码。先和面试官确认题目的边界：元素只有 0、1、2 三种吗？必须原地吗？数组可以为空吗？这些确认过程本身就在展示你的工程思维。然后给出第一个可行方案：计数排序，说明复杂度 O(n) + O(1)。接着主动提出“这个方案扫描了两遍，能不能扫描一遍完成”，顺势引出三指针思路。

在写代码时，边写边解释指针的含义。不要只是默写，最好说出每一行的作用，尤其是遇到 2 交换后curr不前进的理由。写完之后，主动说“我拿一个例子手动跑一遍”，然后选一个不太对称的用例，比如[2, 0, 2, 1, 1, 0]。手动模拟时，把三个指针的位置标清楚，让面试官看到你对不变量有把握。

最后做复杂度分析：时间 O(n)，空间 O(1)，一趟遍历。如果面试官追问稳定性和扩展性，再展开聊三向切分和快排的关系。这套流程走下来，基本上能把“会做”变成“会讲”。

6.2 同类题型的扩展

颜色分类学完之后最大的收获，其实是“用多个指针切分数组”的思维方式。很多高频题都长在同一棵树上。

最经典的是“移动零”。给定数组[0,1,0,3,12]，把 0 移到末尾，同时保持非零元素相对顺序。这就是颜色分类的二元版本，只需要维护一个指针，把所有非零元素按顺序放到前面，剩余位置填 0。

另一个例子是“按奇偶排序数组”，要求把偶数放在前面，奇数放在后面。这也是一次双指针扫描就可以解决的问题。还有快速排序中的三向切分，专门处理大量重复元素。标准快排遇到元素全部相同的时候会退化成 O(n^2)，但三向切分可以把等于基准值的元素集中放到中间，只对小于和大于的部分递归，复杂度能恢复到接近 O(n)。

如果你能把颜色分类吃透，再去看这些题目会特别快。因为它们都在做同一件事：用有限的指针维护若干个有序分区。

以我个人的经验来说，颜色分类这道题最好的学习方式不是背代码，而是把循环不变量写在注释里，然后对照着手动模拟三遍。第一遍用正序用例，第二遍用全相同的用例，第三遍用逆序用例。三遍下来，你就不会再把“遇到 2 后 curr 不动”记错了。面试前如果时间有限，我甚至只复习这一题作为数组双指针的代表，因为它已经涵盖了移动零、三向切分和边界处理的核心套路。最后再给一个小建议：遇到网络上的各种“简单写法”时，先确认它是否清楚地把 p0、curr、p2 三个指针的语义讲明白。能讲明白的写法才是好写法，讲不明白的简写往往是坑。