刷到LeetCode热题100的第93题很多人第一眼看到颜色分类四个字会松一口气——不就是把数组排个序吗等看到进阶要求请使用常数空间、只扫描一遍的算法才意识到事情没那么简单。这道题在LeetCode上的编号其实是75题目叫Sort Colors但在面试圈里更多人叫它荷兰国旗问题。表面上考排序实际考的是双指针和循环不变量的控制能力。这篇文章我会把从暴力解法到荷兰国旗算法的完整思路走一遍把交换、边界、指针移动的每一个细节都拆开讲清楚适合刚开始刷热题100、或者对三指针写法总是记不住的读者。1. 题目到底在说什么三个颜色的乱序数组要原地归位1.1 题目描述与输入输出拆解题目给出一个长度为n的数组里面只有0、1、2三种整数分别代表红色、白色、蓝色。要求按0、1、2的顺序原地排序也就是把所有0放在最前面所有1放中间所有2放最后面。不能额外开一个数组不能调用库里的sort函数。举个具体例子输入nums [2,0,2,1,1,0]输出[0,0,1,1,2,2]这个示例选得很经典。数组里既有2跑到开头的情况也有0跑到末尾的情况普通的冒泡排序需要经过多次相邻交换才能排好。而荷兰国旗算法只需要一次遍历每个元素最多交换一次效率高到你肉眼几乎看不到交换动作。题目里原地的含义是不申请额外数组直接在原数组上做交换操作。进阶要求一共有两条翻译成算法术语就是时间复杂度要达到 O(n)不能是 O(n log n)空间复杂度要是 O(1)也就是常数级额外空间有的中文翻译还会加一句不能使用代码库中的排序函数这些约束本质上是同一件事逼你自己设计一趟扫描完成排序。1.2 为什么这道题会被放进热题100热题100是LeetCode根据不同公司的高频面试题整理出的题单里面并不是所有题都是纯难题但每一道题都代表了一类重要的算法思想。颜色分类排在93/100不是因为它难而是因为它把双指针和循环不变量结合得非常典型面试官特别爱考。我个人的观察是这道题是很多面试者从会写暴力到能讲清楚最优解的分水岭。你会写Arrays.sort(nums)只能说明你用过库函数你能在白板上写三指针代码并讲清楚每一步为什么这样移动指针才说明你真正理解了分区的本质。另外它和快速排序的partition思想一脉相承。理解颜色分类之后再去看LeetCode 215数组中的第K个最大元素、912排序数组里的三路快排优化会觉得顺理成章。所以面试官问这道题的时候很多时候不是考最后的结果而是考你的推导过程。在各大题解区和最近几场周赛的讨论里这道题也经常作为双指针基础题被反复引用属于那种一轮复习必须吃透的题目类型。2. 先聊两种能过但不完美的解法不变量思维缺失下的常见答案2.1 解法一直接用sort排序大部分人的第一反应一定是这题目不就是排序吗那我直接调用排序函数不就行了。确实能过LeetCode上不会报错Java代码就一行public void sortColors(int[] nums) { Arrays.sort(nums); }Python里更简单nums.sort()。时间上是O(n log n)空间看语言版本通常也需要一定的额外栈空间。但这套方案问题很大。第一题目明明只包含0、1、2三种值你却交给通用排序算法处理等于完全没有利用这个关键信息。第二时间上不是最优解O(n log n)在n很大的时候比O(n)慢很多。第三面试官追问能不能只扫描一遍你根本没法接话。通用排序算法是无差别处理它不知道数组里只有三种取值。颜色分类是有特殊结构的知道取值范围只有三种就能设计出更快的算法。你可以把数组想成一盒乒乓球盒子里只有红白蓝三种颜色那你只需要分三个筐来装根本不需要一把一把地比较大小之后再做交换。2.2 解法二统计频次再覆盖写回这是稍微动点脑子之后马上能想到的方案先数清楚0出现几次、1出现几次、2出现几次然后按顺序重新填一遍数组。这个解法很直白Python代码如下class Solution: def sortColors(self, nums: List[int]) - None: count0 count1 count2 0 for num in nums: if num 0: count0 1 elif num 1: count1 1 else: count2 1 for i in range(len(nums)): if i count0: nums[i] 0 elif i count0 count1: nums[i] 1 else: nums[i] 2时间复杂度是O(n)空间复杂度是O(1)看起来已经相当好了。但为什么还不是最优解因为它实际上是两遍扫描第一遍统计数量第二遍把数字写回去。LeetCode原题里的进阶描述写得很明白Could you come up with a one-pass algorithm using only constant space?注意这里的one-pass是整个题目的题眼。面试时如果你给出计数法面试官大概率会继续追问一句能不能只扫描一遍就完成排序到这一步计数法的天花板就出现了它证明了你知道数组只有三种值但没有办法在单次遍历中完成分区。2.3 从两种次优解中提炼核心问题把sort和计数法放在一起对比能提炼出一个核心问题排序的关键不在于数字的大小而在于类别该怎么归位。sort关心的是如何在未知取值空间里做有序排列计数法只利用了取值少这个特点但需要回填一遍真正优秀的解法需要同时做到三件事利用数组里只有0、1、2这三种值的信息只遍历一次数组只通过交换和移动指针完成排序不开额外数组这就是原地一次遍历的精髓。而能满足这三个条件的就是Dijkstra就是提出最短路径算法的那个Dijkstra在他早期论文里讨论过的荷兰国旗问题。他把数组想成一面荷兰国旗国旗由红白蓝三条横带组成数组的排序目标就是把所有红色放到最上面、所有白色放中间、所有蓝色放下。算法通过三个指针维护三个颜色区整个过程只需要一趟扫描非常优雅。3. 荷兰国旗算法三指针如何在一趟扫描里完成三分区3.1 三指针的职责划分荷兰国旗算法的核心是三个指针p0、curr、p2。要掌握它第一步就是把三个指针的职责背到滚瓜烂熟p00区的右边界初始指向数组开头位置0。维护nums[0..p0-1] 全部是0curr当前正在扫描的元素下标初始为0。维护nums[p0..curr-1] 全部是1p22区的左边界初始指向数组末尾n-1。维护nums[p21..n-1] 全部是2在扫描的任意时刻数组被分成四个区间[0, p0)已经处理完毕全是0[p0, curr)已经处理完毕全是1[curr, p2]待处理区域里面还剩0、1、2混合[p21, n)已经处理完毕全是2这四个区间合在一起就是完整的数组。这个结构叫做循环不变量。很多人写三指针代码容易错不是因为交换逻辑不会写而是因为脑子里没有这个区间划分总把三个指针当成三个独立的位置变量。真正的理解方式是每个指针都代表一条分界线而不是一个孤零零的数组下标。我写代码之前喜欢先在注释里把四个区间写下来再动手。等代码写完了再用这个不变量口头验证一遍比自己瞎调试快得多。3.2 三个分支的处理逻辑与背后的推理循环里做的事情非常简单看curr指针指向的数字是0、1还是2分别走三个分支。但每个分支背后都有严格的推理我逐一说清楚。情况一nums[curr] 0说明找到了一个应该放到最前面的0。操作是交换nums[curr]和nums[p0]。交换之后p0位置变成了00区向右扩张一格所以p0。然后curr也因为这轮扫描结束要继续看下一个位置。这里有个关键问题为什么遇到0交换后curr可以放心加1因为交换到curr位置上的数字是原来p0位置上的数字。而原来p0位置上的数字在循环不变量的保证下一定是1除非p0等于curr也就是说p0位置本身就是一个未处理的数字。不管是哪种情况交换回来的数字都不可能是一个还没检查过的0或2所以curr可以前进。情况二nums[curr] 1这种情况最简单因为1就应该待在中间区而curr当前的位置正好落在待扫描区的最左边属于已经在正确位置什么都不用交换直接curr。情况三nums[curr] 2说明找到了一个应该放到最后的2。操作是交换nums[curr]和nums[p2]。交换后p2位置变成了22区向左扩张一格所以p2--。但这个时候curr绝对不能也加1。为什么因为换到curr位置上的数字是原来p2位置上的数字而我们根本没有检查过这个数字。它可能是0可能是1甚至可能是2如果原p2位置本来就存着2的话。下一轮循环还需要用同样的逻辑继续判断当前curr指向的数字所以curr只能原地不动。这是整个算法最关键的难点无数人就是死在这里为什么遇到2交换后不能前进遇到0交换后必须前进。原因就是交换回来的数字有没有被检查过。我刷题的时候把这条规律记成了一句口诀换0前进换2原地等待。很管用。3.3 为什么循环条件是curr p2而不是curr p2循环条件也是一个经典细节答不好很容易露馅。写成while (curr p2)的人通常是把p2理解成普通下标觉得当curr走到p2的位置就算结束了。但这个理解是错的。因为p2是2区的前一位它指向的位置还在待扫描区域内。当curr等于p2时当前这个元素根本还没有被检查过它可能是0、1或者2。如果此时退出循环就会漏掉这个元素。我举个极端例子。数组是[2, 1, 0]初始p00curr0p22。走一遍第一轮nums[0] 2交换nums[0]和nums[2]数组变成[0, 1, 2]p2变成1curr还是0第二轮nums[0] 0交换nums[0]和nums[0]数组不动p0变成1curr变成1这时curr等于p2等于1nums[1] 1还没被处理。如果循环条件是curr p2循环直接退出结果虽然碰巧是[0,1,2]但这是姿势问题换个例子就会错再换个例子[1, 0, 2]第一步curr0发现1前进到1第二步nums[1]0交换后curr2此时currp22nums[2]2确实不用处理但下一次迭代时while真不能停止因为在更复杂的情况下p2位置可能还藏着没检查过的数字。所以标准写法一定是while (curr p2)。4. 完整代码实现与边界用例复盘4.1 三行核心逻辑的完整代码把上面的推理落实成代码其实非常短。Python版本就是刷题社区最常用的写法class Solution: def sortColors(self, nums: List[int]) - None: n len(nums) p0, curr, p2 0, 0, n - 1 while curr p2: if nums[curr] 0: nums[curr], nums[p0] nums[p0], nums[curr] p0 1 curr 1 elif nums[curr] 1: curr 1 else: nums[curr], nums[p2] nums[p2], nums[curr] p2 - 1Java版本的逻辑一模一样只是交换需要临时变量class Solution { public void sortColors(int[] nums) { int p0 0, curr 0, p2 nums.length - 1; while (curr p2) { if (nums[curr] 0) { int tmp nums[curr]; nums[curr] nums[p0]; nums[p0] tmp; p0; curr; } else if (nums[curr] 1) { curr; } else { int tmp nums[curr]; nums[curr] nums[p2]; nums[p2] tmp; p2--; } } } }代码短但千万不要觉得短就容易掌握。面试的时候如果你能主动解释清楚为什么换0后curr要前进、换2后curr不能前进整段代码的可信度会立刻不一样。4.2 边界用例表格复盘写算法题最忌讳想当然。我每次刷完这道题都会用一批边界用例在心里快速跑一遍跑完再提交。下面这个表格是我常用的检查清单输入数组正确输出关键检查点[][]p2-1循环条件不成立直接返回[0][0]单元素所有分支都能覆盖[2][2]单元素且是2交换后p2-1退出[1][1]单元素且是1curr后退出[0,1,2][0,1,2]已经有序算法不产生多余交换[2,1,0][0,1,2]完全逆序考验连续交换[1,0,2][0,1,2]有一个p2位置需在最后一轮处理[2,2,0,0,1][0,0,1,2,2]大量重复元素检验稳定性我以[2,0,1]为例手动走一遍因为这个例子正好覆盖了三个分支初始p00curr0p22nums[0]2与nums[2]交换数组变成[1,0,2]p21curr保持0nums[0]1curr变成1nums[1]0与nums[0]交换数组变成[0,1,2]p01curr变成2此时curr2p21循环条件curr p2不成立结束最终输出[0,1,2]正确这个流程很短但三个分支全部走到是一个非常合适的白板演示用例。4.3 我在实际调试中踩过的两个坑讲两个我自己早年写这道题时真实踩过的坑比背答案有用得多。第一个坑是遇到2交换后手一滑就curr。刷题刷多了的人都知道普通交换算法的习惯是交换完两个指针同时内缩。但荷兰国旗里交换2是单向收缩只有p2动curr留在原地。一旦你把curr也加了从p2换回来的数字就永远卡在当前区域不被检查。我当时在一个类似[2,0,2,1,1,0]的用例上跑出了[0,1,1,0,2,2]这种乱七八糟的结果排查半天才发现是第二个交换多写了一个curr。第二个坑是循环条件写了while (curr nums.length)。这个写法在逻辑上也能跑通因为p2会自动缩小但语义上已经错了它表示我要扫描整个数组而不是我要扫描待处理区域。多扫描到已经确定是2的区域虽然没有致命的后果但会产生无意义的交换而且会让代码的可解释性变差。等面试官问为什么你的循环能处理边界时你很难用一个错误的循环条件自圆其说。养成习惯写成curr p2意义完全对应循环不变量代码和解释直接对得上。5. 颜色分类背后的算法家族从双指针到三路快排5.1 一个思想吃到三道题移动零和移除元素如果真正理解了颜色分类LeetCode 283移动零基本就是送分题。移动零的目标是把所有0移到数组末尾相当于只有0和非0两类的颜色分类。你只需要维护一个p0指针遇到非0元素就跟p0位置交换一路扫下去所有0自然沉底。LeetCode 27移除元素也是一样的思路维护一个写指针遇到不等于val的元素就写入遇到等于val的直接跳过。本质上都是分区思想把数组分成合法区和待处理区用一次扫描把所有不合法的值挪到后面或直接丢弃。所以我一直建议先把颜色分类吃透。这道题刷明白了会感觉后面很多双指针题突然变得简单因为分区思维是通用的。5.2 三路快排颜色分类是快排优化的地基经典快排的partition是两路划分把数组分成小于pivot和大于pivot两部分。但实际工作中经常遇到大量重复元素比如一次要排序的数组里有几万个相同的数。两路划分在重复元素多的时候性能会退化因为等于pivot的元素会被反复交换。三路快排就是荷兰国旗算法的直接应用把数组分成小于pivot、等于pivot、大于pivot三段。等于pivot的区间在下一轮递归里完全不用再处理重复元素越多性能优势越明显。颜色分类可以理解成三路快排的极简版假设pivot固定是1小于1的数字是0大于1的数字是2。你甚至可以用颜色分类的代码去模拟三路快排第一步partition的样子。这也是为什么很多算法教材会把荷兰国旗问题放在快排优化之前讲。5.3 如果题目变成k种颜色怎么办一个很自然的follow-up是如果数组里有0到k-1共k种颜色还能用三指针荷兰国旗吗不能。三指针的前提是只有三种颜色每增加一种颜色就需要增加一个新的分区边界。k种颜色的通用解法是计数排序或桶排序需要O(k)的辅助空间或者用多轮partition每轮固定一种颜色。这也从侧面说明颜色分类之所以用荷兰国旗算法是因为颜色只有三种算法和数据结构是严格配套的没有万能解法。在热题100里颜色分类、腐烂的橘子、基本计算器这类题经常被放在不同分类下刷完颜色分类再去看腐烂的橘子会发现那是BFS图论问题再看基本计算器又变成栈和表达式解析问题。题型完全不同但核心能力都是一样的快速识别题目背后的算法模型。颜色分类教会你的就是看到小范围多值数组第一反应应该想怎么用指针分区。最后说点个人体会。我最早刷这道题的时候看了好几遍题解代码抄下来了但面试模拟时一讲为什么换2不前进就卡壳。后来我换了个办法每次写完三指针代码都强迫自己先口头陈述一遍循环不变量哪些区间已经是0、哪些区间已经是1、哪些区间还是未知。大概坚持了不到一个星期这种分区感就彻底形成了。再回头刷移动零、移除元素甚至复习快排都有一种通了电的感觉。如果你也卡在LeetCode热题100的第93题我建议别急着跳到下一题先把这道题的分区逻辑多讲给自己听几遍绝对不亏。