先交代一下背景我每年都会把这题拿出来给准备跳槽的朋友讲一遍因为力扣 Hot 100 里的“颜色分类”LeetCode 75. Sort Colors可以说是双指针专题里性价比最高的一题。题目本身极其简短就是给一个只有 0、1、2 三种值的数组做原地排序但背后牵扯出的荷兰国旗问题、循环不变量、三路 partition 这些概念几乎能把算法面试的基础能力串起来考一遍。这篇文章适合三类人看一是正在刷力扣 Hot 100、卡在这道题或者背了答案却不懂原理的人二是写过三指针版本但总在边界条件上翻车的人三是想搞清楚“面试官为什么要问这道题、还会怎么追问”的求职者。我会按自己的实战习惯来写先讲清楚题目在考什么再给保底解法然后完整推导一趟扫描的三指针写法最后把调试现场和面试追问一并交代。1. 先把题目看透颜色分类到底在考什么1.1 题目原文与第一反应题目原文不长给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。我们用整数 0、1、2 分别表示红色、白色和蓝色。约束条件是不能使用库里的 sort 函数进阶要求是设计一个仅使用常数空间的一趟扫描算法。我第一次做这题时第一反应和大多数人一样“这有什么难的直接 sort 不就完了”但题目偏偏把“不使用库的 sort 函数”写在最前面这就是在告诉你考点根本不是排序本身而是你能否利用数据分布的特殊结构设计出比通用排序更省时间、更省空间的归类方案。数组里只可能出现三种值这意味着一切基于比较的通用排序算法都是杀鸡用牛刀。你真正需要抓住的信息是“只有三类元素”然后利用这个结构把数组原地分成三段。这个认知一旦建立解法就是水到渠成的事。1.2 从“荷兰国旗”到“颜色分类”经典问题的来由这道题有个更响亮的名字荷兰国旗问题由计算机科学家 Edsger Dijkstra 提出。荷兰国旗恰好是红、白、蓝三色横条把乱序的元素重新归类成三段连续色带的操作和整理一面打乱的国旗非常像所以得了这个名字。理解这个背景不是为了让文章显得有文化而是为了帮你记忆算法结构。你可以把数组想象成三块连续区域最左边一段全是 0红中间一段全是 1白最右边一段全是 2蓝。算法做的所有事情就是维护这三段区域的边界指针一边扫描一边把遇到的元素丢进它该去的区域。手里拽着这个画面代码基本不会写错。1.3 为什么这题能进 Hot 100Hot 100 是力扣根据面试出现频率和知识点覆盖面筛出来的题单颜色分类能稳定占一个名额是因为它一份题量覆盖了三个高频考点原地修改数组考察你能不能摆脱“新建一个数组再拷贝回去”的惯性思维双指针/三指针技巧这是面试中出现频率极高的一类数组处理手法循环不变量思维也就是“每一轮循环结束后数组的哪些部分已经满足什么性质”的抽象能力。这三样东西几乎是所有中等偏上算法题的底层能力。把这题吃透后面再碰“移动零”、“三数之和”、“接雨水”、甚至快排的三路 partition都会觉得似曾相识。很多资料会把“颜色分类”放在双指针分类下但其实它更像一根连接排序和指针两座山的绳子。2. 暴力与计数从最简单的解法说起2.1 直接排序为什么被一口回绝如果你在面试里直接写Arrays.sort(nums)基本等于告诉面试官“我没理解题目的约束”。这里要分清不是 sort 本身有错而是它绕开了出题人想考察的能力。通用排序算法比如快排的时间复杂度是 O(n log n)。对这道题来说数据只有 0、1、2 三类理想的归类时间是 O(n)。面试官期待看到的是你主动发现“这个数组不需要比较排序”这个洞察。所以遇到这种“明明可以调库”的题先停下来想想约束条件到底在暗示什么这是面试里很值钱的一个习惯。2.2 计数排序两遍扫描的稳妥方案最直观且完全正确的解法是计数排序。因为值的范围只有 0、1、2我们可以先遍历一遍统计每种颜色的出现次数再按顺序把数组重新填满。def sortColors(nums): count [0, 0, 0] # 分别记录 0、1、2 的出现次数 for num in nums: count[num] 1 idx 0 for color in range(3): for _ in range(count[color]): nums[idx] color idx 1这段代码逻辑简单到几乎不可能出错第一遍统计第二遍回填。时间复杂度 O(n)空间复杂度因为计数数组大小固定为 3同样算 O(1)。如果你在面试时一时紧张没想出三指针先写这个版本是完全可以拿分的甚至可以主动跟面试官说“这是两趟扫描的思路我可以再优化成一趟。”这句话本身就是加分项。2.3 计数排序的局限与面试官的心思两遍扫描有什么问题吗单看复杂度没有任何问题常数空间、线性时间已经满足题目的大部分要求。但进阶要求里明确写了“一趟扫描算法”面试官想要的往往就是这个 one-pass 版本原因有两个第一一趟扫描强制你使用指针维护区域边界这才能考察你对数组索引和交换细节的掌控力。写两遍扫描的人不需要思考“换回来的元素是什么”自然练不到这块。第二真实工程里的流式场景可能只允许数据读一遍或者数组大到希望减少写回次数一趟扫描确实更贴近实际需求。我的建议是两遍扫描当保底方案三指针当主答案。先写正确拿分再给优化方案比一上来就背三指针、结果边界处理得一塌糊涂要稳得多。毕竟面试是按点给分代码正确永远排在“解法炫酷”前面。3. 一趟扫描搞定三指针的完整推导3.1 三指针的循环不变量先说结论维护三个指针left、mid、right整个循环过程中数组始终保持下面这个状态[0, left)区间内全部是 0红色[left, mid)区间内全部是 1白色(right, len-1]区间内全部是 2蓝色[mid, right]区间内是尚未处理的元素这种“每轮循环结束后数据满足什么性质”的描述就是算法里常说的循环不变量。写代码时只要保证每轮操作后不变量仍然成立循环结束时左边是 0、中间是 1、右边是 2答案自然就对了。为什么要用三个指针而不是两个因为数组要被分成四部分零区、一区、待处理区、二区四个分区需要三条分界线。两个指针最多只能切出三段装不下“已处理的 1”和“待处理的数据”这两个不同的区。想通这一点你就能理解为什么这道题是“三指针”而不是“双指针”。3.2 分情况讨论0 怎么办、1 怎么办、2 怎么办mid指针负责扫描整个待处理区每轮只看nums[mid]的取值分三种情况等于 0这个元素应该放到最左边的 0 区。把nums[left]和nums[mid]交换然后left和mid都向右移动一位。为什么mid可以跟着动因为交换过来的nums[left]只可能是 0 或 1——如果left mid换的是同一个元素必然是 0如果left midnums[left]原本属于 1 区必然是 1。无论哪种情况换到mid位置的值都是“已归类”的不会破坏中间一区的性质所以mid可以放心前进。等于 1白色本来就该待在中间区域什么都不交换直接mid跳过。等于 2这个元素应该放到最右边。把nums[mid]和nums[right]交换然后只移动right--mid不能动。原因很关键nums[right]是未被处理过的元素它可能是 0、1 也可能是 2换到mid位置后必须再看一遍所以mid要停在原地留到下一轮继续检查。这三句话就是整个算法的核心。面试官最常抓的细节就是第三行交换 2 之后mid动不动。这块逻辑想明白了代码就是照抄。3.3 完整代码与复杂度结论def sortColors(nums): left, mid, right 0, 0, len(nums) - 1 while mid right: if nums[mid] 0: nums[left], nums[mid] nums[mid], nums[left] left 1 mid 1 elif nums[mid] 1: mid 1 else: # nums[mid] 2 nums[mid], nums[right] nums[right], nums[mid] right - 1循环结束后所有 0 都在最前面所有 2 都在最后面中间的 1 自然归位。复杂度方面一趟扫描每个元素至多被处理两次被换到mid位置后可能再次被检查整体 O(n)只用了三个指针变量空间 O(1)。这已经顶到这道题的最优复杂度了。用 C 或 Java 写也是同一套逻辑只是数组交换的写法略有差异思路完全一致。为了确认正确性我建议手动走一遍nums [2, 0, 2, 1, 1, 0]过程如下表轮次leftmidright操作数组状态初始005-[2, 0, 2, 1, 1, 0]1005nums[0]2与 nums[5] 交换right--[0, 0, 2, 1, 1, 2]2004nums[0]0自交换leftmid[0, 0, 2, 1, 1, 2]3114nums[1]0自交换leftmid[0, 0, 2, 1, 1, 2]4224nums[2]2与 nums[4] 交换right--[0, 0, 1, 1, 2, 2]5223nums[2]1mid[0, 0, 1, 1, 2, 2]6233nums[3]1mid[0, 0, 1, 1, 2, 2]结束243mid right退出已有序这个表建议你亲手画一遍画完你会彻底理解“为什么第 4 步换回 2 之后不动 mid”。4. 实操踩坑边界、死循环与调试实录4.1 最经典的 bug交换 2 之后不动 mid我见过太多第一次写三指针的人在else分支里下意识写成“交换后 mid、right--”然后结果完全不对甚至直接死循环。问题就出在交换回来的那个元素nums[right]在交换前是未处理数据它要是 0 呢此时把 0 换到了mid位置mid却直接跳过去了这个 0 就永远没人再检查最终数组中必然出现错位。我自己面国内大厂时就写错过一次面试官没直接说答案只问了一句“你确定换回来的元素一定是 2 吗”我当时愣了一下手动模拟了一遍才意识到问题。这种错误特别容易在紧张时犯所以我现在的习惯是写完后立刻拿[1, 2, 0]这种三个数的小用例在脑子里过一遍能快速暴露这类边界 bug。4.2 循环条件用 还是 标准写法是while mid right因为mid指向待处理区域的第一个元素right指向待处理区域的最后一个元素mid right时这个位置还没被检查。如果你写成mid right会漏掉mid right时那一个元素。举个具体例子nums [0, 1]初始left0, mid0, right1处理完nums[0]0后left1, mid1此时mid right这个位置上的 1 还没被检查但mid right会让循环直接退出。这个例子里 1 恰好就在正确位置看不出问题换个场景就可能翻车。所以循环条件要写配合交换逻辑天然正确终止不会因为多检查一个“已归位”的元素而出错。4.3 内存与稳定性为什么这道题不在乎“稳定排序”有同学会问三指针的交换是跳跃式的会不会破坏原有顺序答案是不需要关心因为这道题根本不要求稳定排序。所有 0 都是等价的你无法区分、也不需要区分“第一个 0”和“第二个 0”排序完成后它们看起来一模一样。所以交换可以非常随意。但如果你将来处理的是“按某个 key 分类同时还要保持同类元素的原始相对顺序”那就不能这么随便交换了得考虑稳定 partition 或者引入临时数组。这个差别我建议你记在笔记里面试被追问“你这个交换稳定吗”时能讲清楚“这道题不需要稳定”和“什么场景需要稳定”是很加分的区分度。5. 面试追问与延伸从 3 色到 k 色5.1 面试官爱问的三个 follow-up据我观察面试官在这道题之后基本都会追加问题出现频率最高的是下面三个“如果数组里不止 3 种颜色改成 4 种呢”三指针的核心假设是中间区域只保留一种值4 色情况下中间要维护两类值三个指针不够用需要调整策略或者换回计数排序。“如果要求尽可能少的交换次数呢”三指针并不是交换次数最优的方案。更优做法是先按计数的三段边界确定每个元素的目标位置然后只交换错位的元素。这个变体更适合作为拓展题思考面试时能说出“三指针不是最少交换方案”就已经超出多数人了。“这个思路和快排有什么关系”三指针本质上就是三路快排的 partition 过程把等于 pivot 的元素单独放中间小于和大于的分别放两边。理解了这一点“颜色分类”就不再是一个孤立题目而是快排优化的重要前置知识。5.2 延伸四色、k 色怎么处理如果是固定 4 种颜色可以把三路分区的思想推广成四路分区维护四个边界指针但逻辑复杂度上升得很快写起来容易出错。更通用、更稳妥的方案是回到计数排序统计每种颜色出现次数后线性回填时间复杂度仍是 O(n)空间复杂度 O(k)。因为颜色种类是有限常数这块额外空间可以忽略不计。如果颜色种类 k 和数组长度 n 同阶问题性质就变了要么允许 O(k) 的额外空间要么退化成基于比较的排序。这个“k 是常数还是可变”的判断标准比死记某种解法更有通用价值。我面试别人时其实更看重候选人能不能讲出这条判断链路而不是背出某一种实现。5.3 我的刷题体会与复盘建议最后讲点我自己的方法。我做这道题时没有急着写代码而是先在草稿纸上画出三个区间把三个指针的初始位置标出来然后手动模拟一个[2, 0, 2, 1, 1, 0]的完整过程。模拟完一遍再去写代码基本一遍过。这个习惯我一直保留着处理任何指针类题目都适用——先让指针在纸上跑起来代码只是把跑的过程翻译成语法。复盘时我会把两条容易错的细节写进错题本一条是“交换 2 之后为什么不动 mid”另一条是“循环条件为什么是 ”。这两条才是面试真正考察的东西不是你能不能背出三行交换代码而是你对索引和不变量的掌控力。如果你也在刷力扣 Hot 100我的建议是把这道题和“移动零”“三数之和”“快排的三路 partition”放在一起对比着看你会发现它们的本质都是用指针把数组切分成若干区域。刷通这一组题双指针这个专题基本就拿下了。