如果你刷过LeetCode热题100大概率会在某一天点开一道叫“颜色分类”的题目。这题乍一看很简单给一个只包含0、1、2的数组排个序完事。但等你真正动手写代码会发现它远不是一个sort就能交差的题目——题目明确不让用库函数而且进阶要求是“仅用常数空间、一趟扫描”。我第一次做这题时第一反应是“就这”结果被双指针的细节折磨了一晚上。这篇文章会把颜色分类的来龙去脉、三种核心解法、边界条件和踩坑经验完整拆开讲希望能帮正在刷热题100的你少走点弯路。1. 热题100里的常青树颜色分类到底在考什么1.1 一眼看懂题目三色排序的本质题目描述不长但信息量不小。给定一个包含红色、白色、蓝色共n个元素的数组原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。为了简化题目用整数0、1、2分别表示红色、白色、蓝色。换句话说输入是类似[2,0,1,1,0,2]这样的数组输出必须是[0,0,1,1,2,2]。本质是什么它不是比较排序的问题而是一个“数据分区”问题。因为数组中只有三类值排序后的结果必然是所有0在最左边接着是所有1最后是所有2。所以问题完全等价于“把数组原地分成三段”。你不需要维护元素之间的相对顺序是否稳定也不需要关心最大值最小值只需要把三类数字各自归位。由于每个数字只有三种可能算法题里把这种问题归类为“三色问题”或“荷兰国旗问题”。如果你之前没有接触过分区思想很容易掉进“直接调用排序函数”的陷阱里。但题目明确说了不能使用库内置的sort函数。这句话不是故意为难你而是逼你去想线性扫描的方案。1.2 为什么说这题是“双指针入门试金石”刷题刷到一定量你会发现很多数组题都在考一个核心能力用指针维护一段区域的边界。颜色分类作为LeetCode热题100中的一题正是双指针模型的经典代表。它不像“两数之和”那样两指针相向而行也不像“滑动窗口”那样双指针同向移动而是“三指针划分三块区域”。很多人的误区在于认为只要会用for循环和swap双指针就没啥可学的。实际上颜色分类完美暴露了新手对“循环不变量”的模糊理解。你可能会盯着while i right发呆为什么不是i n为什么交换2之后i不能后移这些细节如果没想明白看答案时觉得自己懂了下次遇到同类题照样不会写。所以它是检验你对指针边界、交换时机、循环条件是否真正理解的试金石。能白板默写出颜色分类并讲清楚每一步为什么这样做才算真正跨过了双指针的入门门槛。1.3 适合谁刷、怎么刷收益最大从刷题人群看这题覆盖三个层次刚开始刷LeetCode的初级者可以用它来理解“数组原地操作”和“指针分区”准备面试的求职者可以用它来演示自己对边界条件的敏感度想强化算法功底的进阶者可以用它作为三路快排和荷兰国旗问题的跳板。我的建议是刷这题时不要直接看答案先按“统计数量后回填”写一版再自己思考“能不能一趟扫描完成”。哪怕第一版双指针写得稀烂也比直接抄答案有价值。因为你在思考过程中会真正体会到为什么交换0和交换2的指针处理不一样。这种体验是任何讲解都无法替代的。2. 从暴力到优化三种解法的演进与选型2.1 第一反应统计计数然后回填看到只有0、1、2三种值最直觉的解法就是计数排序。遍历一遍数组数出0、1、2分别出现了多少次然后按顺序把数组重新填满。这个方法简单到几乎不可能写错时间复杂度是O(n)空间复杂度是O(1)如果用固定三个变量。def sortColors(nums): cnt0 cnt1 cnt2 0 for x in nums: if x 0: cnt0 1 elif x 1: cnt1 1 else: cnt2 1 idx 0 for _ in range(cnt0): nums[idx] 0 idx 1 for _ in range(cnt1): nums[idx] 1 idx 1 for _ in range(cnt2): nums[idx] 2 idx 1这段代码严格使用了额外三个变量确实符合O(1)空间。但注意它遍历了数组两遍第一遍统计第二遍回填。而题目进阶要求“一趟扫描”。所以它虽然是最稳的解法但不是面试官期待的最优解。还有一个细节需要注意如果写nums[:cnt0] [0] * cnt0Python会临时创建一个列表这就不再是严格的O(1)空间。在面试或机试时这个小细节会被面试官抓到。所以即使写计数排序也建议用循环回填而不是切片赋值。2.2 进阶标准答案荷兰国旗双指针荷兰国旗问题由计算机科学家Dijkstra提出题意正好对应荷兰国旗的三色条纹。它的精妙之处在于用三个指针维护三条边界一次遍历把数组分成0区、1区、未处理区、2区四个部分。先定义四个区间[0, left) 区间全部是0[left, i) 区间全部是1[i, right] 区间待处理(right, n-1] 区间全部是2。这里特别强调right本身指向的是待处理区间的最后一个元素不是已经排好的2区。初始化时left 0i 0right n - 1。当i穿过right时未处理区间为空整个数组就变成0区、1区、2区三块连续区域。这个算法的核心是三条规则如果nums[i] 0说明当前元素应该放进左端的0区。把nums[i]和nums[left]交换然后left右移i继续右移如果nums[i] 1说明它本来就在中间位置i直接右移如果nums[i] 2说明它应该放进右端的2区。把nums[i]和nums[right]交换然后right左移但i不能移动。第三点是最容易错的地方。交换过来的元素可能是0、1、2中的任意一个必须留在“待处理”位置重新判断一次。很多人在这里习惯性地写i结果代码越跑越乱。2.3 冷门但有趣的变体先排0再排1除了荷兰国旗还有一种“分步分区”的思路第一趟把所有的0放到最前面第二趟再把所有的1放到0后面。实现上可以用一个left指针维护已排好0区的边界遇到0就交换之后再用一个left指针从0区末尾开始把1也如法炮制。这种方案的时间复杂度同样是O(n)但需要两趟扫描空间O(1)。好处是逻辑更好理解新手很容易写对。它的缺点是两次扫描增加了常数倍的开销而且没有充分利用“三种值依次排列”的对称性。在面试中如果你先给出这个解法再引出荷兰国旗的一趟扫描会让面试官觉得你有递进思考的过程。还有些人喜欢用类似快排partition的写法先以1为基准把小于1的放左边大于1的放右边。这个思路本质也是双指针但因为基准选取方式不同实现细节和荷兰国旗略有差异。你可以把荷兰国旗理解为“同时以0和2两个基准做partition”它比单基准partition更彻底。2.4 三种方案对比表时间、空间、稳定性解法核心思路时间复杂度空间复杂度扫描趟数代码难度适用场景计数排序回填统计0/1/2数量后循环回填O(n)O(1)2趟低第一次刷题练手分步分区先排0再排1两次双指针O(n)O(1)2趟中低理解分区过程荷兰国旗双指针三指针一趟扫描O(n)O(1)1趟中面试最优解从工程角度说这三种解法都能在毫秒级解决n 10^5的数据量性能差异几乎可以忽略。但从面试考察角度说荷兰国旗双指针无疑是核心考点。它展示了你对“一趟扫描”和“原地交换”的理解深度这也是它被收入热题100的原因之一。3. 一步步手写荷兰国旗算法细节决定成败3.1 双指针的定义与循环不变量先明确三个指针的含义这一步如果不清楚后面的代码一定写不好。left指向0区右边界的下一个位置。也就是说nums[0...left-1]全是0i当前遍历到元素的下标。nums[left...i-1]全是1right指向2区左边界的上一个位置。也就是说nums[right1...n-1]全是2而nums[i...right]是待处理区间。初始化时left 0i 0right n - 1。三个区间都为空或未处理0区和2区为空待处理区间是整个数组。循环条件是while i right。我见过很多人写成while i n这会在某个特殊场景下出错。因为当i越过right后待处理区间已经为空此时继续向右扫描只会把已经归位的2区又拖回未处理区。用i right作为条件本质是“只要还有未处理元素循环就继续”。3.2 核心交换逻辑什么时候动左指针什么时候动右指针把交换逻辑拆开看第一种情况nums[i] 0。我们把nums[i]与nums[left]交换。交换完成之后原来nums[left]的值会来到i位置。根据循环不变量nums[left]只可能属于1区当left i时或者它就是i自己当left i时。两种情况都不会导致新来的元素是0或2。所以i可以安全地右移一位。交换后left扩展0区i继续处理下一个元素。第二种情况nums[i] 1。当前元素本来就处于正确区域只需要把i右移一位。第三种情况nums[i] 2。我们把nums[i]与nums[right]交换。交换完成之后原来nums[right]的值会来到i位置。这个值我们完全没有见过它可能是0、1、2中的任意一个。因此i不能右移而是必须原地再判断一次新来的值是什么。同时right--因为此时位置right的元素已经被确认为2可以把它划入2区。从这段分析可以看出不是所有交换之后都要移动i。正确地区分“交换0”和“交换2”的后续动作是写好这题的关键。很多人死记硬背“交换0就i交换2就不动”却不知道原因这很容易在代码变形题上翻车。3.3 边界条件全梳理i指针的移动规则边界条件主要围绕三个场景空数组或长度为1。当n 0时right初始为-1while i right直接不成立。当n 1时初始化i0right0循环进入一次后i或right移动循环正常结束。所以荷兰国旗算法天然处理了极端边界不需要单独特判。全部是2的情况。例如[2,2,2]。left 0i 0right 2。第一次交换nums[0]和nums[2]right1i仍为0第二次交换nums[0]和nums[1]right0i仍为0此时i0right0进入循环。注意现在nums[0]依然是2所以交换nums[0]和nums[0]right-1i仍为0。循环条件不成立结束。最终数组不变全部是2正确。全部是0的情况。[0,0,0]。left0i0right2。每次遇到0交换nums[i]和nums[left]其实是自己和自己lefti。最终循环结束数组不变正确。全部是1的情况。[1,1,1]。每次遇到1i循环结束数组不变正确。这些边界情况说明荷兰国旗算法的循环条件i right非常优雅不需要额外判断。但也提醒我们交换0时可能进行无意义的自身交换这在代码上没有问题只是略微多了一点点操作。3.4 完整代码实现Python/C版理解了指针定义和交换规则写代码就是顺理成章的事。Python代码def sortColors(nums): n len(nums) left, i, right 0, 0, n - 1 while i right: if nums[i] 0: nums[i], nums[left] nums[left], nums[i] left 1 i 1 elif nums[i] 1: i 1 else: nums[i], nums[right] nums[right], nums[i] right - 1C代码class Solution { public: void sortColors(vectorint nums) { int left 0, i 0, right nums.size() - 1; while (i right) { if (nums[i] 0) { swap(nums[i], nums[left]); } else if (nums[i] 1) { i; } else { swap(nums[i], nums[right--]); } } } };Java代码的写法也基本一致class Solution { public void sortColors(int[] nums) { int left 0, i 0, right nums.length - 1; while (i right) { if (nums[i] 0) { swap(nums, i, left); } else if (nums[i] 1) { i; } else { swap(nums, i, right--); } } } private void swap(int[] nums, int a, int b) { int tmp nums[a]; nums[a] nums[b]; nums[b] tmp; } }建议大家在本地多跑几组用例。尤其是[2,0,1]、[1,2,0]、[2,0,2,1,1,0]这种看起来有迷惑性的用例能帮你快速发现自己实现中的边界问题。4. 实测与复杂度为什么一趟扫描能比计数排序更快4.1 时间复杂度与空间复杂度的真相计数排序和荷兰国旗算法的时间复杂度都是O(n)从大O记号上看完全一样。但实际运行中荷兰国旗算法只需要一趟遍历而且每次遇到1不会进行交换只有遇到0或2才发生交换。计数排序需要两趟遍历一趟统计、一趟回填。对于大型数组两趟遍历的常数倍差距虽然不夸张但在高频场景下也能感受到差异。空间复杂度方面两者都可以做到O(1)。但要特别注意实现细节计数排序如果使用Python的切片赋值会创建临时列表那就不再是严格的O(1)空间。所以我在前面强调用循环回填代替切片。荷兰国旗算法的交换过程完全在数组内进行任何语言都不会产生额外数组。4.2 交换次数分析并不是每次都交换很多人以为双指针解法会进行很多交换实际上没那么夸张。扫描过程中遇到1时不交换只移动i遇到0时交换一次同时移动left和i遇到2时交换一次只移动right。最坏情况下例如数组全部是2每次都要交换但交换后right不断左移i始终指向同一个已被换成2的位置最终交换次数为n次。最好情况下数组全部是1一次交换都没有。平均情况下交换次数大致等于数组长度的一半左右仍然是非常少的常数。对比计数排序虽然统计阶段没有交换但回填阶段需要给大量元素重新赋值。赋值操作和交换操作的成本相差不大。因此荷兰国旗算法在常数因子上还有优势。4.3 实测用例与常见错误输出我整理了一组测试用例建议你在写完代码后全部过一遍输入数组期望输出说明[][]空数组[0][0]单元素0[1][1]单元素1[2][2]单元素2[2,0,1][0,1,2]完全倒序[1,0,2][0,1,2]中等混淆[2,0,2,1,1,0][0,0,1,1,2,2]常规混合[0,0,0][0,0,0]全0[1,1,1][1,1,1]全1[2,2,2][2,2,2]全2如果某个用例输出不对可以用一个小技巧在每次交换后打印left、i、right以及整个数组观察指针运动是否符合循环不变量的定义。这种方法比单步调试更快定位逻辑错误。4.4 与库排序的对比为什么题目禁止sort库排序是通用的比较排序时间复杂度通常是O(n log n)也有一些实现会对近乎有序的数组做优化但它并不知道“数组元素只有0、1、2”这个额外信息。颜色分类的进阶要求就是希望利用这一信息把时间降到线性。从工程实践来看如果数组元素的值域非常小比如0到2计数排序和荷兰国旗分区都是非常高效的选择。而在真实业务中如果数据只有少数几种类别你也不需要调用通用排序完全可以自己写一个线性分区函数。这就是这道题除了面试之外的现实价值它训练你在特定条件下放弃通用工具寻找更轻量、更定制化的方案。5. 从颜色分类到真实业务迁移思维才是刷题的意义5.1 三色问题的业务映射数据分区、权限分级很多人刷题时觉得算法和实际工作隔得很远但颜色分类这个模型其实非常贴近真实业务。举个例子一个用户列表里每个用户有三种状态——管理员、普通用户、访客。你想把列表原地整理成“管理员在前、普通用户在中、访客在后”这就和颜色分类一模一样。只是把0、1、2替换成了枚举类型或状态标记。再做细一点如果某个系统需要按照“待审核、审核通过、审核拒绝”三种状态对工单进行分区而且要求不新建数组、只做原地重排颜色分类的荷兰国旗解法可以直接改造成一个函数。只要把判断条件从数值比较换成状态判断即可。这类分区操作在很多批处理场景中很常见。数据清洗、日志分级、权限归位本质上都是“把有限类别的数据按照既定顺序排列”。理解了颜色分类你就掌握了处理这类问题的最小核心。5.2 一个思想的延伸快速排序里的三路划分荷兰国旗问题更著名的应用是快速排序的优化。经典的快排在处理大量重复元素时如果选到重复值可能递归退化。三路快排把数组分成三部分小于基准、等于基准、大于基准。这样等于基准的元素一次性全部归位不需要再参与后续递归。颜色分类就是三路快排最简化的版本基准固定为0和2分区结果是小于1、等于1、大于1。你在理解颜色分类时学到的“交换后是否移动i”的判断正是三路快排中最容易出错的细节。从这个角度看刷颜色分类不是孤立的它是通往更复杂排序算法的台阶。5.3 变种题清单同思路还能解哪些题学完一个算法后我习惯找同思路的题目来巩固。与颜色分类共享“数组分区”思想的高频题至少有以下几类移动零把数组中的0移到末尾保持非零元素相对顺序。这本质是两色分区也可以用双指针解决数组奇偶排序把偶数放前面、奇数放后面或者反过来也是双指针分区的变体按基准分区给定一个基准数把小于基准的放左边大于基准的放右边这是快排partition的直接体现三值排序的其他变体例如数组是三个字母A/B/C要排序成A/B/C你完全可以套用荷兰国旗解法。当你发现这些题目都能用同一套“循环不变量 交换”的模板解决时你对指针的理解就上了一个台阶。5.4 刷题建议如何用这道题组建自己的解题模板我的建议是不要死记硬背代码而是把核心框架抽象出来维护两个分区边界一个是左区的右边界一个是右区的左边界中间是待处理区域。每一次循环根据当前元素所属的类别决定是扩左区、扩右区还是原地不动。写下这个框架之后再遇到新的分区题先问自己三个问题当前元素属于哪个区交换后从交换位置过来的元素是否还需要再次判断哪个指针需要移动把这三个问题想清楚任何双指针分区题都不会难住你。这也是我从颜色分类中收获最大的地方它让我建立了“指针对应循环不变量”的思维模式而不再是被动地套模板。6. 踩坑实录我周围人在这题上摔过的跟头6.1 坑一忘记处理nums为空或长度为1的情况一些写法在开头会写if not nums: return之类的边界判断但对荷兰国旗算法来说这个判断其实是多余的。因为right n - 1在空数组时为-1while i right直接不成立函数自然返回。单元素数组也同样被循环条件覆盖。但问题在于如果你用的是“分步分区”或“计数排序”的写法可能就没这么幸运。比如在两层循环里依赖nums[i1]这类越界访问空数组就会直接报错。所以递归式和循环式的越界风险不同最好每种写法都在本地跑一遍边界用例。6.2 坑二循环条件写成i n而不是i right我第一次写这题时就把它写成了while i n。表面上看i最大会扫到数组末尾似乎没问题。但实际上一旦right已经移动到i的左边待处理区间就为空了这时的扫描就开始破坏已经排好的2区。举个例子输入[2,0,1]。用i n的写法i0right2交换2和1数组变为[1,0,2]right1然后i0遇到1ii1遇到0交换nums[1]和nums[left0]数组变为[0,1,2]left1i2此时i2right1i已经大于right但i n仍成立继续进入循环。nums[2]是已经排好的2把它当作2处理交换nums[2]和nums[right1]数组又变成[0,2,1]right0。循环继续最终输出错误。这就是把循环条件写错带来的典型后果。6.3 坑三使用while循环时忘了更新指针交换2的分支里有些人会忘记right--导致数组长度不变但指针一直停在原地程序陷入死循环。或者交换0的分支里只写了left忘记i导致同一个位置的0被反复交换。调试这类问题最好的办法是打印每轮循环后的nums、left、i、right。看到指针没有按照预期移动问题往往一目了然。6.4 坑四受“排序”二字影响总想用sort题目明明有一句话说不准用库排序但还是有人抱着侥幸心理写nums.sort()。这种写法在面试里等于零分因为题目考察的正是“如何在线性时间内手工完成分区”。有的面试官会接着说“如果不限制sort你当然可以sort但那样这题的意义就不存在了。”所以刷题时可以给自己一个硬性要求凡是看到“不能使用库函数”一定是想让你实现某个线性或特定复杂度的替代方案。6.5 针对初学者的自测用例集最后送上一组完整自测用例帮助你在提交前快速验证test_cases [ ([], []), ([0], [0]), ([1], [1]), ([2], [2]), ([2,0,1], [0,1,2]), ([1,0,2], [0,1,2]), ([2,0,2,1,1,0], [0,0,1,1,2,2]), ([0,0,0], [0,0,0]), ([1,1,1], [1,1,1]), ([2,2,2], [2,2,2]), ([0,1,2,0,1,2], [0,0,1,1,2,2]), ] for nums, expected in test_cases: before nums[:] sortColors(nums) assert nums expected, f失败: {before} - {nums}, 期望 {expected}把这些用例放到本地跑一遍如果全部通过基本可以放心提交。如果哪组失败回到第4.3节用打印指针的方式来排查通常很快能找到问题。