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 0current 0right 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加1current加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加1left位置之前的所有元素都已经是被扫描处理过的并且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 - 1C版本class Solution { public: void sortColors(vectorint 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]这个例子在草稿纸上跑一遍。初始化left0current0right5。数组[2, 0, 2, 1, 1, 0]。第1步current0指向2。2应该去右边交换nums[0]和nums[5]数组变成[0, 0, 2, 1, 1, 2]right变为4current保持不变。第2步current0指向0。0应该去左边交换nums[0]和nums[0]自己和自己left变为1current变为1。数组不变[0, 0, 2, 1, 1, 2]。第3步current1指向0。交换nums[1]和nums[1]left变为2current变为2。数组不变[0, 0, 2, 1, 1, 2]。第4步current2指向2。交换nums[2]和nums[4]数组变成[0, 0, 1, 1, 2, 2]right变为3current保持2。第5步current2指向1。1属于中段current变为3。第6步current3此时right也是3循环条件current right依然满足。nums[3]是1current变为4。第7步current4 right3循环结束。最终数组为[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遇到问题按这三处检查基本都能解决。第一个Bugwhile (current right)。这个改了之后结果永远是差一点。原因前面已经详细说过current right时还站着一个尚未检查的元素。有人可能会反驳“如果current和right指向同一个位置那这个位置肯定已经检查过了呀”不对。right是从最右边向左移动的current从最左边向右移动两者相遇的那个下标只被right的移动逻辑接触过并没有被current完整判断过。所以循环条件必须包含等号。第二个Bugnums[current] 2时交换后current。这是最隐蔽的一个。你需要构造一个右边换回来的元素是2的用例才能稳定复现问题。比如[0, 2, 1, 2, 0, 2]第一步current1指向2交换nums[1]和nums[5]数组变成[0, 2, 1, 2, 0, 2]right变成4如果此时current右边界推进就不彻底。这个bug的恶心之处在于它不是每次都对结果有影响换回来的元素是0或1时可能“碰巧正确”换回来是2时就直接错。排查方法很简单在2分支结束后不要动current。第三个Bugleft和current的更新顺序搞反。0分支里有些人会先把left加1再做交换这样left指向的位置就不是正确的0边界。记住固定写法先交换再left加1再current加1顺序不要拆。left和current互相独立但更新时机必须确保“交换发生在正确的边界上”。第四个Bug忽略了“原地修改”的约束直接创建新数组返回。LeetCode的函数签名已经写了返回void或者None所有修改必须落在原数组上。C版本尤其明显传入的是vector 你创建新数组属于挂羊头卖狗肉。面试时这样写会被直接判为不符合要求。4.2 高频错误速查表错误现象可能原因修复方式排序后第一个元素不对while循环用了漏掉了currentright的位置改成current right末尾总残留2且顺序乱2分支交换后current换来的新元素没被再判断2分支只做right--current不移动0区域不连续中间夹着1left和current更新顺序写反边界被提前推进先交换再left再current运行报错或返回空值没有在传入数组上原地修改直接修改nums不要返回新数组这张表是我在评论区经常看到的问题汇总覆盖了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”的原因用一句话解释清楚就说明真正掌握了。我的解释是左指针保证换过来的一定是已处理元素右指针换过来的是未知元素未知元素必须留在原地重新判断。这句话也是我在面试现场向面试官讲这道题时说的第一句话。