企业官网建设流程全解析

LeetCode热题100刷到第93题，终于轮到这道被无数人当成“入门必做”的颜色分类（75. Sort Colors）。说实话，这道题难度标的是Medium，但它在面试里的地位一点都不低。基础解法谁都会：遍历一遍统计0、1、2的个数，再重新填回去。但题目末尾那行“你能想出一个仅使用常数空间的一趟扫描算法吗”才是真正的考点，也正是这行字，让这道题从“会调sort库就能AC”变成了“考察三指针和循环不变量理解”的经典题。这篇文章我就从暴力解法一路讲到三指针最优解，把指针移动规则背后的“为什么”彻底讲透，再把我自己调试时踩过的坑和排查方法全部整理出来。

1. 题目拆解与思路演进

1.1 原题到底在说什么

题目给了一个数组，里面只有0、1、2三种数字，分别代表红色、白色、蓝色。要求原地对它们进行排序，让相同颜色的元素相邻，并按照红白蓝的顺序排列。换句话说，最终数组应该是一串0、一串1、一串2。

如果你直接调用语言自带的排序函数，一行代码就结束了，但那就完全失去了这道题存在的意义。题目明确追加了两条约束：一是“原地”，不能开新数组返回；二是“常数空间的一趟扫描算法”。这两条约束实际上就是在暗示你：别用暴力统计，别用额外数组，必须用指针在原来的数组上倒腾。

这一类“只包含少量不同元素”的排序，本质上不是比较排序。很多人的第一反应是“为什么不能直接快排”，快排是基于比较的排序，计算复杂度在平均情况下是O(nlogn)，在这道题里属于降维打击，但性能并不是最优。因为元素种类限定为3种，完全可以利用“有多少个0就放多少个0、有多少个1就放多少个1”的分配思想，把复杂度压到O(n)。

这道题的学术背景也很值得一提，它源自计算机科学家Dijkstra提出的“荷兰国旗问题”。荷兰国旗有红白蓝三色，和这里的0、1、2完全对应。Dijkstra当年设计这个算法的初衷，是为了解决排序中“重复键值很多”的场景，用一个单次遍历完成三向切分。现在这个思想被广泛用在三路快排中，也就是把小于pivot、等于pivot、大于pivot的三组元素在一次遍历里分好。所以刷这一道题，等于顺便理解了后面三路快排的partition部分。

1.2 从暴力解到最优解，思路是怎么一步步被逼出来的

先看最直白的写法：第一遍扫描统计0出现次数count0、1出现次数count1、2出现次数count2，然后从下标0开始重新填充数组。这个解法时间复杂度O(n)，空间复杂度O(1)，能AC，但不满足“一趟扫描”的进阶要求。很多人会疑惑：既然能AC，为什么还要费劲学三指针？因为在真正的面试场景里，面试官可以通过追问“能不能用一趟扫描完成”，直接判断你是在背答案，还是真的理解了指针如何在数组上做partition。

如果要求一趟扫描并且常数空间，思路就必须转换：不能先数数再回填，必须在扫描的过程中就把数字放到它们应该待的位置。放到哪？0往左边放，2往右边放，剩下的中间自然都是1。

这就要用到三指针：一个指针left负责维护“0区域的右边界”，一个指针right负责维护“2区域的左边界”，一个指针current负责从左往右遍历。current每走到一个位置，就看当前位置是什么数字。是0，就扔到左边；是1，直接跳过；是2，就扔到右边。扔到右边的元素可能是0也可能是1，所以current不能急着往前走，要再检查一次；扔到左边的情况则不一样，因为左边界左边全是已经处理过的0，从左边换回来的元素只可能是1，这个位置就算处理完了，current可以直接前进。这个差异是整个算法最核心、也最容易写错的地方，下一节专门讲。

2. 三指针算法的核心细节与实现

2.1 三个指针各管什么事

初始化：left = 0，current = 0，right = nums.length - 1。三个指针各自的含义：

• left：下一个0应该被放到的位置，同时也是已经排好的0区域右侧的下一个空位。它维护的是“0区域”的边界。
• right：下一个2应该被放到的位置，同时也是已经排好的2区域左侧的前一个空位。它维护的是“2区域”的边界。
• current：当前正在检查的元素下标，负责从左到右扫描整个数组。

循环条件写作 while (current <= right)。为什么是“小于等于”而不是“小于”？因为当current和right相遇时，right指向的这个位置还没有被current检查过，它可能是0、1、2中的任何一个，需要再处理一次。如果写成current < right，指针一旦相遇就跳出循环，会漏掉最后一个位置的数字，导致排序不完整。这个边界是很多第一次写的人最容易翻车的地方。

进入循环后分三种情况处理：

第一种，nums[current] === 0。说明这个元素应该放到左侧0区域。交换nums[current]和nums[left]，然后left加1，current加1。

第二种，nums[current] === 1。1本来就该待在中段，不需要动，current加1继续往后看。

第三种，nums[current] === 2。说明这个元素应该放到右侧2区域。交换nums[current]和nums[right]，right减1。这个时候注意，current不能加1，因为从右边换过来的新元素是未知的，需要回到当前位置再判断一次。

2.2 最容易出错的点：同样是交换，为什么current的移动规则不一样

我刷这道题的时候，第一次就被绊在这里：numscurrent == 2时交换完，习惯性写了current++，结果出现了一个很隐蔽的bug，数组末尾总有元素没被排好。

原因要从“换回来的是什么”说起。当current不等于right时，当前位置的新元素是从right位置换过来的。right这个位置由于还没被扫描过，它可能是0，可能是1，也可能是2。如果是0，交换后当前位置得到0，那不能跳过，要留在原地把这个0再送到左边去；如果是1，那当前位置就是1，直接跳过没问题；如果是2，说明这个元素依然要去右边，必须继续交换。所以交换后current不能动，这样才能确保每一个被换过来的元素都被正确归位。

反过来看nums[current] == 0时，为什么可以放心让current加1？left位置之前的所有元素都已经是被扫描处理过的，并且left指针始终不会超过current，所以left位置上要么是1，要么是已经处理过的0。更关键的一点是，当把left位置的值和current位置的值交换后，换到current位置来的元素只能是1。因为如果left位置是0，它早就该被交换走了；left位置如果是1，换到current位置依然是1。所以交换后，current位置是一个已经确定处理过的数字，自然可以放心加1。

如果你非要在0分支里也写成“交换后不移动”，理论上通过二次判断也能得到正确答案，但代码会多出很多无意义的比较，可读性也会变差。三指针之所以简洁，正是依赖“从左边换回来的一定安全”这个不变量。理解了这个不变量，你就掌握了这道题90%的精髓。

2.3 Python与C++实现参考

Python版本，这是我在LeetCode提交时用的版本：

class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ left, current, right = 0, 0, len(nums) - 1 while current <= right: if nums[current] == 0: nums[current], nums[left] = nums[left], nums[current] left += 1 current += 1 elif nums[current] == 1: current += 1 else: nums[current], nums[right] = nums[right], nums[current] right -= 1

C++版本：

class Solution { public: void sortColors(vector<int>& nums) { int left = 0, current = 0, right = nums.size() - 1; while (current <= right) { if (nums[current] == 0) { swap(nums[current], nums[left]); ++left; ++current; } else if (nums[current] == 1) { ++current; } else { swap(nums[current], nums[right]); --right; } } } };

两个版本逻辑一模一样，没有特殊情况，也没有奇奇怪怪的优化。这道题考察的就是对循环不变量的理解，核心代码短到不能再短。

时间复杂度O(n)，因为每个元素最多被current访问一次，某些元素可能因为交换被多看一眼，但即使如此次数也是常数级别，整体依然是线性。空间复杂度O(1)，只用了三个额外变量。

3. 实操过程与调试实录

3.1 用完整用例走一遍指针变化

写代码只是第一步，真正检验你有没有理解，是拿一个典型用例一步一步推指针。我用nums = [2, 0, 2, 1, 1, 0]这个例子在草稿纸上跑一遍。

初始化：left=0，current=0，right=5。数组：[2, 0, 2, 1, 1, 0]。

第1步：current=0指向2。2应该去右边，交换nums[0]和nums[5]，数组变成[0, 0, 2, 1, 1, 2]，right变为4，current保持不变。

第2步：current=0指向0。0应该去左边，交换nums[0]和nums[0]（自己和自己），left变为1，current变为1。数组不变：[0, 0, 2, 1, 1, 2]。

第3步：current=1指向0。交换nums[1]和nums[1]，left变为2，current变为2。数组不变：[0, 0, 2, 1, 1, 2]。

第4步：current=2指向2。交换nums[2]和nums[4]，数组变成[0, 0, 1, 1, 2, 2]，right变为3，current保持2。

第5步：current=2指向1。1属于中段，current变为3。

第6步：current=3，此时right也是3，循环条件current <= right依然满足。nums[3]是1，current变为4。

第7步：current=4 > right=3，循环结束。最终数组为[0, 0, 1, 1, 2, 2]，排序正确。

这个例子特别能说明一个问题：为什么self-swap频繁出现？因为left和current可能指向同一个位置，这时候交换自己和自己并不会影响数组，但代码逻辑上还是先交换、再移动。很多人在第2步、第3步会觉得“这不是多此一举吗”，甚至想直接去掉交换，改成nums[left] = 0之类的赋值操作，结果写出一个包含覆盖逻辑的版本，后面遇到0和2交错的情况就会丢数据。我的建议是：老老实实统一用swap，不要针对self-swap做特殊优化，代码越统一越不容易出错。

3.2 边界条件与自测用例

写完代码我通常跑一组固定用例，确保所有分支都被覆盖到。推荐的自测集合：

• 空数组：[]，应保持为[]。
• 单元素数组：[0]、[1]、[2]，应保持原样。
• 全是0：[0,0,0]，应保持为[0,0,0]。
• 全是2：[2,2,2]，应保持为[2,2,2]。
• 0和2交替：[2,0,2,0]，排序后应为[0,0,2,2]。
• 已经排好序：[0,1,2]，应保持不变。
• 完全逆序：[2,1,0]，排序后应为[0,1,2]。
• 经典乱序：[2,0,2,1,1,0]，排序后应为[0,0,1,1,2,2]。

其中[2,0,2,0]这个用例很有价值，它能检验出在“只有0和2”的情况下算法是否依然正确，也能暴露current在交换后是否错误地移动。你可以在本地用任意语言把这些用例包一层断言跑一遍，如果全部通过，基本说明这题的实现没有低级错误。

还有一个隐藏比较深的边界是数组长度很大、0和2特别多、1特别少的情况。这种数据下right指针会快速左移，current和right的相遇时机直接影响循环是否提前退出，你可以丢给LeetCode的随机大数组用例直接验证，跑一遍通过就说明边界处理没有大问题。

3.3 从另一个角度验证：计数排序也能过，为什么还要选三指针

这里额外说说为什么LeetCode会接受计数排序但面试官不一定接受。计数排序的代码写着很短：

class Solution: def sortColors(self, nums: List[int]) -> None: count = [0, 0, 0] for x in nums: count[x] += 1 i = 0 for color in range(3): for _ in range(count[color]): nums[i] = color i += 1

这个版本时间复杂度O(n)，空间O(1)，因为它只用了固定大小为3的计数数组，严格讲也算常数空间，所以能AC。但它是两趟扫描：第一趟统计，第二趟覆盖。从性能上看两者差距很小，但从算法训练的角度看，三指针版本更贴近“分区排序”的思想，这也是Dijkstra荷兰国旗问题的本意。

所以你在网上会看到很多讨论“颜色分类能不能用计数排序”，我的建议是：追求AC，两种都可以；追求对算法的理解，一定要把三指针写熟练。因为三指针训练的是对下标边界、交换行为、循环不变量的敏感度，这类能力在很多数组类题目里都会用到。

4. 常见错误与排查技巧

4.1 4个高频Bug

我第一次做这道题时，连续提交错三次，后来总结出下面4个常见Bug，遇到问题按这三处检查基本都能解决。

第一个Bug：while (current < right)。这个改了之后结果永远是差一点。原因前面已经详细说过，current == right时还站着一个尚未检查的元素。有人可能会反驳：“如果current和right指向同一个位置，那这个位置肯定已经检查过了呀？”不对。right是从最右边向左移动的，current从最左边向右移动，两者相遇的那个下标，只被right的移动逻辑接触过，并没有被current完整判断过。所以循环条件必须包含等号。

第二个Bug：nums[current] == 2时交换后current++。这是最隐蔽的一个。你需要构造一个右边换回来的元素是2的用例，才能稳定复现问题。比如[0, 2, 1, 2, 0, 2]，第一步current=1指向2，交换nums[1]和nums[5]，数组变成[0, 2, 1, 2, 0, 2]，right变成4，如果此时current++，右边界推进就不彻底。这个bug的恶心之处在于它不是每次都对结果有影响，换回来的元素是0或1时可能“碰巧正确”，换回来是2时就直接错。排查方法很简单：在2分支结束后不要动current。

第三个Bug：left和current的更新顺序搞反。0分支里，有些人会先把left加1，再做交换，这样left指向的位置就不是正确的0边界。记住固定写法：先交换，再left加1，再current加1，顺序不要拆。left和current互相独立，但更新时机必须确保“交换发生在正确的边界上”。

第四个Bug：忽略了“原地修改”的约束，直接创建新数组返回。LeetCode的函数签名已经写了返回void或者None，所有修改必须落在原数组上。C++版本尤其明显，传入的是vector &，你创建新数组属于挂羊头卖狗肉。面试时这样写会被直接判为不符合要求。

4.2 高频错误速查表

这张表是我在评论区经常看到的问题汇总，覆盖了90%的提交失败场景。你提交报错时，先对照表里四种情况查一遍，比自己瞎调试省时间得多。

4.3 和类似题目串起来学，一道题打通一个类型

这道题做完之后，我建议做三件事巩固。

第一件事：把同构的题目放在一起对比。最典型的是LeetCode 283「移动零」。移动零其实可以看成颜色分类的退化版：数组里只有0和非0两类，要求把0移动到末尾，同时保持非0元素的相对顺序。它的解法和三指针里的0分支很像，但要求保持非0的顺序，所以不能直接交换，要用快慢指针把非0元素逐个前移，最后统一补0。对比这两道题，能让你看清“同一思想在不同约束下如何变种”。

第二件事：研究标准三路快排的partition写法。三路快排的核心就是把小于pivot、等于pivot、大于pivot的三段在一次遍历里分好，和颜色分类完全同构。理解了颜色分类，三路快排的partition代码对你来说就是改个比较条件的事。这个扩展价值比AC一道题重要得多。

第三件事：把“三指针维护三段区间”的模板记进脑子里。以后遇到“把数组分成三组”的题，比如奇偶分组、正零负分组，都可以套这套思路。核心就是先确定三段区间分别由哪些指针维护，再确定遍历指针遇到每一类元素时该交换到哪里、自己动不动。

提示：这道题有一个潜在陷阱是——虽然算法是一次遍历，但数组元素的相对顺序并不会被保留。比如[2, 0, 1, 0, 2]排序后变成[0, 0, 1, 2, 2]，两个0先后的顺序可能因为交换被打乱。这道题本身不要求稳定排序，所以没问题。但如果哪道题改成“保持同类元素原顺序”，三指针就不再适用，需要改用计数排序的稳定版本。看清题目要求再动手。

最后再分享一个我刷这类Medium题时的习惯：每做完一道题，我都要求自己用中文把“为什么这样写”讲一遍，讲不清楚的地方就是理解有洞的地方。颜色分类这道题，你只要能把“current遇上0时交换后加1，遇上2时交换后不加1”的原因用一句话解释清楚，就说明真正掌握了。我的解释是：左指针保证换过来的一定是已处理元素，右指针换过来的是未知元素，未知元素必须留在原地重新判断。这句话也是我在面试现场向面试官讲这道题时说的第一句话。