颜色分类问题解析：双指针与荷兰国旗算法详解

LeetCode刷题之路继续更新，今天聊聊第75题“颜色分类”。这道题在很多人的刷题清单里是绕不开的一道中等题，原因很简单：它考察的东西很底层，就是怎么在一个数组上通过交换完成排序，而且限制条件很苛刻——只允许原地操作、只能用常数级额外空间、只扫描一遍。这三个条件叠加起来，就把很多“想当然”的解法全部堵死了。如果你面试投的是后端或者算法岗，这道题被拿来当现场笔试题的概率不低，因为它短小精悍，能快速检验一个人对指针操作和循环不变量的理解。

这道题还有个特别经典的别名，叫“荷兰国旗问题”，基本所有刷题的人都听过这个名字。题目本身不复杂：给你一个数组，里面只有0、1、2三种数字，要求你把它排成0在前、1在中间、2在后的顺序。看起来很简单对吧？直接排个序就结束了。但如果真直接调用排序函数，那就完全掉进陷阱了。这道题真正的价值在于，它教会你一种比普通排序更轻量、更高效的处理思路——利用固定范围的取值和双指针的配合，把时间复杂度压到O(n)、空间复杂度压到O(1)。这篇内容适合正在刷LeetCode准备校招或者社招的朋友，也适合那些想系统补一下“双指针”“循环不变量”基础的人，认真读完并动手实现一遍，收获会比单纯背题大得多。

1. 整体设计与思路拆解：从“三色问题”看算法考点

1.1 这道题的常见误区：排序函数真的能用吗

先说一个很多人第一次做这道题的心理活动：数组里就0、1、2三种数，直接Arrays.sort()或者sorted()不就完了？这种思路对不对？从结果上看是对的，数组确实有序了，从面试评分上看是零分。

原因有两条。第一，题目明确要求“原地”排序，也就是不能新建数组再拷贝回去，而很多排序方法在底层会额外申请空间，这已经不再满足“常数级额外空间”的约束。第二，这道题想考察的不是你怎么调用现成的API，而是你能不能利用数组取值只有三种这一特殊性质，设计出更高效的线性扫描算法。调用排序函数的时间复杂度是O(n log n)，但这道题完全可以做到O(n)。在数据量大的场景下，这个差异是很明显的。

所以拿到这道题，第一件事不是写代码，而是先理解出题人的意图：这是一个"数组取值有限"的排序问题，最优解法应该利用这个限制条件去做文章，而不是走通用排序的老路。

1.2 为什么双指针是首选方案：复杂度对比

在正式动手写代码前，可以先从复杂度角度梳理一下各种方案的优劣，这能帮你理解为什么最终解法长那个样子。

一个最朴素的方案是：第一遍遍历数组，数出0、1、2各有多少个，第二遍再把数组重新填一遍。这个方案时间复杂度O(n)，空间复杂度O(1)，看似已经满足所有约束了，但它的问题是“扫描了两遍”。如果题目没有强制“只扫描一遍”，这其实是完全可用的方案。但很多场景会进一步要求“只做一趟遍历”，这就逼你换思路。

而双指针方案可以做到真正意义上的“一趟扫描完成排序”，过程中每个元素最多被处理一次。它的核心思想是：在数组上维护三个区域——左边全是0，右边全是2，中间全是1。随着指针移动，这三个区域不断扩张，最终整个数组被瓜分完毕。

我把各种方案的差异整理成了一张对照表，方便你直观感受：

从对照表可以清楚看到，双指针方案在扫描次数上独一档，这也是它在面试中最受青睐的原因。面试官想看到的不是你会不会排序，而是你能不能根据题目特性调整策略。

1.3 荷兰国旗问题的本质：区间划分思想

这道题为什么叫“荷兰国旗问题”？因为荷兰国旗恰好是红白蓝三色构成的条纹。把三种颜色类比成0、1、2三种数字，问题就成了“让同色条纹汇聚在一起”。这个类比背后藏着一个更通用的算法思想：区间划分。

区间划分的核心逻辑是：不直接考虑“怎么把这个元素放到正确的位置”，而是思考“当前这个元素应该属于哪个区间”。在颜色分类这道题里，我们把数组想象成三条平行通道：

• 通道0：接收所有0，从左边往右扩展
• 通道2：接收所有2，从右边往左扩展
• 中间剩下的自然全是1

这个过程有点像整理书架上的书：你不是把所有书倒出来重新排，而是从左往右走，看到A类书就放到左边区域，看到C类书就丢到右边区域，B类书不动，走到头书架自然就整理好了。双指针的本质，就是把“整理动作”翻译成数组下标和交换操作。

2. 核心细节解析与实操要点：双指针的两种写法

2.1 第一类写法：维护三个区域的循环不变量

这道题最经典、也最容易理解的双指针写法，是通过维护一个循环不变量来完成的。什么叫循环不变量？简单说，就是在每次循环结束后，你都能保证数组满足某个固定规律，这个规律不随循环次数变化而改变。

在这道题里，我们需要维护三个指针：

• left：指向目前所有0区域的下一个位置，也就是下一个0该放的地方
• right：指向目前所有2区域的前一个位置，也就是下一个2该放的地方
• i：当前正在扫描的位置

每一步都保证这样一个不变式：left左边的区间全是0，right右边的区间全是2，而i和left之间夹着的全是1。初始的时候，left = 0，i = 0，right = n - 1，三个区域都是空的，这个不变式天然成立。然后你让i从左侧一直向右移动，直到和right相遇。

每一次循环里分三种情况处理，循环不变式始终不会破坏：

• 如果nums[i] == 0：把nums[i]和nums[left]交换，然后left++，i++
• 如果nums[i] == 1：直接i++，什么都不做
• 如果nums[i] == 2：把nums[i]和nums[right]交换，right--，但i不要动

很多人在这个环节会卡住：为什么nums[i] == 2时交换完，i不能加一？原因在于，我们刚刚从right位置换过来的那个元素，可能是0、1、2中的任意一个，它还没被检查过。如果此时直接i++，就会跳过这个新换过来的元素，导致排序结果错误。这是这道题最重要的细节，没有之一。

用Python实现出来是这样的：

def sortColors(nums): left, i, right = 0, 0, len(nums) - 1 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

这个写法很稳，因为每一步都有明确的语义：0往左边送，2往右边送，1留在原地。代码简单，但要真正做到默写无误，你得先把那个“2交换后i不动”的原因刻在脑子里。

2.2 第二类写法：双指针从两边同时收拢

除了维护三区域的经典写法，还有另一种直观性稍差但同样正确的方案：只用两个指针，left负责把0往左放，right负责把2往右放，但两个指针的移动逻辑略有不同。

这种写法的思路是先从左侧找到第一个2，从右侧找到第一个非2，然后进行交换。每次交换后继续收拢区间。实现起来长这样：

def sortColors(nums): n = len(nums) left = 0 right = n - 1 # 先把左边的2都丢到右边去 while left < right: while left < right and nums[left] == 0: left += 1 while left < right and nums[right] == 2: right -= 1 if left < right and nums[left] == 2: nums[left], nums[right] = nums[right], nums[left] right -= 1 elif left < right and nums[left] == 1: # 遇到1暂时跳过，继续找后面的2 left += 1 # 此时数组里只剩下0和1还没完全就位 # 再做一遍类似操作，把1归到中间 left = 0 right = n - 1 while left < right and nums[left] == 0: left += 1 while left < right: while left < right and nums[right] != 1: right -= 1 while left < right and nums[left] == 0: left += 1 if left < right: nums[left], nums[right] = nums[right], nums[left] left += 1

说实话，这个写法我一般不推荐给初学者，因为它的逻辑分支比第一种多，边界条件也更绕，稍不注意就会出现死循环或漏处理。我把它列出来，是想让你知道“双指针”不是只有一个固定模板，关键是你得真正理解每个指针的功能边界在哪里。如果你自己写的时候理不清，就老实回归第一种写法，那才是性价比最高的选择。

2.3 两种写法的取舍建议

从我刷题的实际体验来看，针对面试场景，第一种“三指针循环不变量”写法是首选。它的代码量最短、逻辑分支最少、记忆成本最低，而且只要想清楚“交换后i是否自增”这一个关键点，整个实现就是稳的。

第二种写法虽然也是双指针，但本质上把一段逻辑拆成了两个阶段，代码量和心智负担都偏大。如果你是那种需要在面试现场手写并讲清楚的人，我会强烈建议你只掌握第一种，把它练到闭着眼都能写出来，然后在讲解时把循环不变量说清楚，面试官基本就会点头。

如果你的目标是纯粹刷题增加题库量，两种都写一遍也有好处，可以加深对指针控制的理解。但优先级上，第一种一定排在前面。

3. 实操过程与核心环节实现：以具体输入为例手把手推演

3.1 测试用例准备与预期输出

在写代码之前或者写完之后，建议先准备好几个测试用例，尤其是那些容易出错的边界情况。颜色分类这题，我常用的测试用例有这么几组：

标准混合场景[2,0,2,1,1,0]是题目自带的示例，也是我每次写完代码第一个跑的用例。因为它包含了三种元素互相穿插的情况，能一次性检验结果是否正确。

3.2 手把手推演：每一轮循环发生了什么

我们拿[2,0,2,1,1,0]来完整走一遍第一种写法的循环过程，看看每次交换后数组长什么样。初始状态设left = 0、i = 0、right = 5：

第一轮：nums[i] = nums[0] = 2，需要往右边送。交换nums[0]和nums[5]，数组变成[0,0,2,1,1,2]，然后right减一变成4。注意此时i仍然是0，因为我们还没有检查换回来的那个元素是什么。

第二轮：继续看nums[i] = nums[0] = 0，需要往左边送。交换nums[0]和nums[left]，因为left = 0，所以实际上就是和自己交换，数组不变，还是[0,0,2,1,1,2]。left变成1，i变成1。

第三轮：nums[i] = nums[1] = 0，又是个0，继续往左边送。交换nums[1]和nums[1]，数组依旧不变，left变成2，i变成2。

第四轮：nums[i] = nums[2] = 2，往右边送。交换nums[2]和nums[4]，数组变成[0,0,1,1,2,2]，right变成3。

第五轮：当前i = 2，right = 3，继续执行。nums[i] = nums[2] = 1，这种情况最简单，啥也不用做，直接i++，i变成3。

第六轮：此时i = 3，判断循环条件i <= right，也就是3 <= 3，满足，继续。nums[3] = 1，直接i++，i变成4。

第七轮：i = 4，right = 3，4 <= 3不成立，循环结束。最终数组是[0,0,1,1,2,2]，完美符合预期。

这个推演过程看起来很简单，但你有没有注意到一个问题：第五轮和第六轮连续遇到两个1，都直接跳过了，没有被交换。这正是这个算法的精妙所在——所有的1其实不是被“移动”到正确位置的，而是别人0和2相互交换时，它们自然留在了中间。理解这一点，你就抓住了这个算法的灵魂。

3.3 从推演中沉淀出的三条代码纪律

上面这个推演过程看似顺畅，但实际写代码时，很多人会栽在几条不起眼的细节上。我根据自己的实战经历，总结出三条代码纪律，你可以在写代码时对照检查：

第一条纪律：循环条件统一写成while i <= right，不要写成while i < right。为什么？因为当i指向的元素是2时，我们交换后right--，但i不动。如果此时i == right，说明还有一个元素没检查，循环需要再跑一次。如果你写的是i < right，就会提前退出，导致一个元素没有被处理。

第二条纪律：处理2时的交换顺序是nums[right], nums[i] = nums[i], nums[right]，交换后right减一，i绝对不能变。这一点在推演里的第一轮已经展示过了。原因我再重复一遍，因为这是考试时最容易暴露问题的地方：换过来的nums[i]还没被检查过，你无法确定它是0还是1还是2。

第三条纪律：处理0时left++和i++要同时进行，不能只加一个。从推演的第三轮可以看到，left和i有时候指向同一个位置，有时候i在left右边。如果你只加left不加i，就会反复检查同一个位置的0，导致死循环。

3.4 复杂度验证：是否真的达标

完成代码后，可以随手做一次复杂度验证。遍历过程中，每个元素最多被操作一次（交换算一次），所以时间复杂度是O(n)，这里n是数组长度。额外变量只有left、i、right三个整数，空间复杂度是O(1)。数组交换全部在原地完成，不申请额外内存。这三个维度都满足题目要求，解法合格。

我实测过几组不同长度的随机数组，包括长度为1万、10万、100万的输入，执行时间都是线性增长，没有任何异常波动。对于只有三种取值的数组来说，这个解法在时间上的表现已经是天花板了，因为哪怕只是看一遍所有元素，你也至少需要O(n)的时间。

4. 常见问题与排查技巧实录：那些年我在这道题上踩过的坑

4.1 为什么用for循环会导致结果错误

这道题最普遍的一个坑，就是有人会把指针移动写成for i in range(n)。表面看起来也是让i从左走到右，但for循环的问题在于，每轮结束时i的变动不是你控制的。也就是说，当你处理完一个2、需要“原地再检查一次”时，for循环强行把i加一了，那个从右边换过来的元素就被跳过了。

我曾经见过一个初学者写的版本，用for i in range(n)处理[2,0,2,1,1,0]，最后输出结果是[0,0,1,2,1,2]，看着就差一点，但就是不对。这个例子特别好地解释了“换过来的元素必须再检查一遍”这个核心规则。所以我的建议是：凡是用双指针做原地交换的题，统一用while，不要用for，因为for循环的递增机制和双指针的灵活控制本质上是冲突的。

4.2 数组全为同一种数字时会不会死循环

有人会担心一个问题：如果数组全是2，比如[2,2,2,2]，那nums[i] == 2的分支会一直触发，right一直减，i保持不变，这不是死循环吗？

答案是不会。你可以手推一遍：i = 0、right = 3时，交换nums[0]和nums[3]（都是2），right变2。接着i = 0、right = 2，交换nums[0]和nums[2]，right变1。再接着i = 0、right = 1，交换后right变0。此时i = 0、right = 0，循环条件0 <= 0还成立，再交换一次nums[0]和nums[0]，right变成-1，循环结束。整个过程没有重复交换两个相同的固定位置，因为每次交换都会让right收缩，所以循环必然终止。

同理，如果数组全是0，每次交换都是自己和自己，i和left同步前进，也不会死循环。如果数组全是1，那就是最简单的纯跳过，更不会出问题。这三种极端情况都可以用白名单用例来测试。

4.3 换位后right指向的值有没有正确处理

还有一种比较容易出错的场景：当i位置的元素是2，但right位置的元素恰好也是2时，你把两个2交换了，白白浪费一次操作。这不算错误，因为right照样左移、循环迟早会结束，但从效率角度看是多余的交换。

优化这个细节并不复杂：当nums[i] == 2时，可以先循环把right向左移动，跳过所有已经是2的元素，再做交换。但我不建议为了这点微小优化给代码增加复杂度，因为大多数场景下，数据量到不了需要节省那几次交换的程度。在面试现场，简单正确的代码永远比极致优化的代码得分高。

4.4 面试现场怎么讲这道题才能拿高分

这道题如果出现在面试里，光是写对代码还不够，讲解思路的能力也很重要。我建议按这样一个逻辑组织你的讲述：

第一步，先说明题目自身的特殊约束：只有三种取值，所以不用通用排序，可以做线性扫描。第二步，抛出“区域划分”的核心思想：用三个指针把数组维护成三个区间。第三步，详细介绍循环不变量：left左边全是0，right右边全是2，中间待处理。第四步，分三种情况展示指针如何移动。第五步，强调一个易错点：遇到2交换后i不能动。

按这个顺序讲，层层递进、逻辑清晰，面试官听起来非常舒服。很多同学习惯上来就写代码，写完才讲思路，这会显得思路凌乱。先讲设计、再动手实现，是面试中最稳妥的节奏。

4.5 常见问题速查表

我把平时刷题群里大家问得比较多的问题整理成了表格形式，你可以把它保存下来，做题前快速过一遍：

5. 相似题型的延伸与应用：这个解法还能用在哪里

5.1 按奇偶排序：双指针的平价用法

LeetCode上有一道题是“按奇偶排序数组”，要求把所有偶数放在奇数前面。这个题和颜色分类思路高度相似：只不过把0和2的区分，换成了偶数和奇数的区分。你可以用两个指针从数组两端出发，左边找奇数、右边找偶数，然后交换。代码量比颜色分类还少，算是这个思路的入门级变体。

这类题的价值在于让你意识到：双指针不仅仅用于“有序数组的查找”，它还可以用在“按条件对数组进行分类整理”上。只要你判断清楚了分类标准和边界情况，指针移动逻辑几乎可以套用。

5.2 数组去除特定元素：原地算法的延伸实践

还有一道“移除元素”的题，要求原地删除所有等于给定值的元素，并返回新长度。这个题也能用双指针解决，只不过一个指针遍历、另一个指针记录“下一个合法位置的写入点”。

颜色分类给你的训练在于：你已经习惯了把一个指针当作“写入指针”，另一个指针当作“扫描指针”，这种思维迁移到移除元素的题上会很顺畅。它们本质上都在做“原地重排”，只是判断条件不同。

5.3 实际工程中的类比：内存分区的思想相通

如果你将来接触过数据库或者存储系统，会发现这种“按区间划分数据”的思想不是刷题专用。比如内存分配器维护空闲块和已用块、日志系统按级别分流消息、消息队列按优先级区分分区，这些场景里你都能看到“不同数据进不同通道”的影子。

我在实际写代码时也有过类似的体验：处理一批带有状态字段的对象时，需要把它们按状态分别存放，当时第一反应就是想起颜色分类的三指针逻辑。虽然工程代码比算法题复杂得多，但核心的指针位移思想是相通的。

5.4 一题多练的建议：刻意练习胜过盲目刷题

这道题做完了，建议你马上找两到三个变体继续练手。比如把0、1、2换成A、B、C三个字符的字符数组排序，把三个区间扩展到四个区间，或者把数组改成链表看看怎么处理。每一次变体训练，都会强化你对指针控制的理解。

我自己刷题的经验是：与其一天刷十道没消化透的题，不如一道题吃透之后做三轮变体训练。颜色分类这道题，就属于典型的高性价比训练素材，值得花一整个晚上专门研究。

6. 一点经验总结与最后的个人感受

走到这里，这道题的完整脉络已经非常清楚了：从最初的题目理解，到双指针设计，再到交换细节的推演，最后到面试表达和变体延伸。整个过程下来，你会发现真正困难的从来不是“写出能跑的代码”，而是“想清楚每一步为什么这样写”。颜色分类这道题好就好在，它用最简单的数据结构、最少的代码量，把一个极其重要的算法思想——区间划分——展现得淋漓尽致。

最后再分享一个我自己的小习惯：每次刷完一道和双指针相关的题，我都会顺手在纸上画出整个推演过程的数组变化图，标出每一轮left、i、right的位置变化。这个习惯帮我避开了许多边界条件的坑。做多了你会发现，所谓的“边界条件敏感”不是天生的，而是靠一次次手推培养出来的。希望这篇内容对你有用，去把代码敲一遍，再把推演过程默写一遍，这题就真正变成你的了。