刷 LeetCode 的朋友应该都懂刷到一定阶段最让人头疼的往往不是那些需要奇技淫巧的难题反而是那种“看着简单一写就错”的题目。75题“颜色分类”就是这么一道典型的题。说它经典是因为它背后是鼎鼎大名的荷兰国旗问题说它恶心是因为如果你没见过三指针的解法很容易陷入“排序但又不让用排序”的思维陷阱里出不来。今天这篇就把这道题从头到尾拆开把思路踩过的坑以及最优解的写法一次说透。这道题表面上是给你一个包含0、1、2的数组让你原地排序使得相同数字相邻且按0、1、2的顺序排列。但它真正的考点不是排序算法本身而是“一次遍历 常数空间”的原地分区能力。很多人在面试里被这道题卡住就是因为没意识到它考察的是双指针/三指针的灵活运用而不是真的让你调一个快排或者计数排序。适合正在准备算法面试的开发者、刷题卡壳需要思路点拨的新手以及想深入理解“分区思想”的人来读。1. 先看清楚题目在问什么1.1 题目描述与直观理解题目输入是一个只包含0、1、2的整数数组你要做的是原地排序。注意几个约束条件不能使用库函数sort不能新开额外的数组空间复杂度要求O(1)。看起来非常基础但你真要动手写会发现很多常规排序思路在这里都不适用。我最早刷这道题的时候第一反应是“这不就是计数排序吗”数一下0有几个、1有几个、2有几个然后重新填回去。这个思路完全正确但问题是需要额外空间存储计数而且严格来说如果题目要求“一趟扫描”完成计数排序需要两趟一趟计数一趟填数。而这道题的最优解能做到一趟扫描这就是它经典的地方。题目还有一个隐晦的坑数组元素只有0、1、2三种。这意味着你可以利用这个特性做分区而不需要比较交换那种通用逻辑。换句话说这不是一个“通用排序”问题而是一个“按值域分区”问题搞清楚这一点解题方向就对了。1.2 从“荷兰国旗问题”说起这道题的学术背景是荷兰国旗问题由计算机科学家Dijkstra提出。想象一条竖线左边是红色中间是白色右边是蓝色目标是让所有同色区域连在一起。放到这道题里就是左边全部是0中间全部是1右边全部是2。理解了这层背景你就明白为什么经典解法是“三指针区域划分法”——本质上就是维护三个区域不断把当前元素归入正确的颜色区。我第一次看到这个背景的时候觉得有点装——排序就排序跟国旗有什么关系但后来才知道这种分区的思路在很多场景下都有用比如快速排序中的三路快排就是类似的思想把数组分为小于pivot、等于pivot、大于pivot三部分。如果你以后刷到和快速排序变种相关的题目这个思路会反复出现。所以这道题不只是一道题它是一个模型的敲门砖。关键认知这道题考核的不是“你会不会排序”而是“你会不会设计分区逻辑”。2. 解法演进从计数排序到三指针2.1 方案一计数排序能过但不够优雅计数排序的思路最简单先遍历一遍数组数出0、1、2分别有多少个然后再遍历一遍数组按顺序重写。def sortColors(nums): count0 count1 count2 0 for num in nums: if num 0: count0 1 elif num 1: count1 1 else: count2 1 idx 0 for _ in range(count0): nums[idx] 0 idx 1 for _ in range(count1): nums[idx] 1 idx 1 for _ in range(count2): nums[idx] 2 idx 1这个代码是能通过OJ的时间复杂度O(n)空间复杂度是O(1)因为计数变量只有三个。但要知道这是在输入值域有限时才能用的小技巧。如果面试官追问“如果数组里不只是0、1、2而是0到k你的方法还行不行”这个方案就不灵了。更关键的是它扫描了两遍数组虽然大O还是O(n)但“一趟扫描”是这道题更优解的一个卖点。2.2 方案二三指针就地划分正餐三指针的思路说起来非常直观但实现的时候特别容易写乱。我们维护三个指针left指向下一个要放0的位置初始为0right指向下一个要放2的位置初始为n-1cur当前遍历的位置初始为0遍历规则如果nums[cur] 0和nums[left]交换left和cur都加1如果nums[cur] 1cur加1即可如果nums[cur] 2和nums[right]交换right减1cur不动为什么nums[cur]2时cur不能动因为交换过来的nums[right]可能是0也可能是1这个值还没检查过必须留在下一轮处理。这是一个核心细节不是无意义的小动作。def sortColors(nums): n len(nums) left, cur, right 0, 0, n - 1 while cur right: if nums[cur] 0: nums[left], nums[cur] nums[cur], nums[left] left 1 cur 1 elif nums[cur] 1: cur 1 else: nums[right], nums[cur] nums[cur], nums[right] right - 1 return nums很多人第一次写的时候会写成cur和right交换后cur也加1然后就会导致边界bug。下面我会详细解释为什么不能加。2.3 为什么说三指针是最优解三指针的时间复杂度是O(n)空间复杂度是O(1)而且只遍历一趟。从任何维度来看它都达到了这道题的理论下界——因为你要判断每个元素的值至少得看一遍数组。常数空间的限制也卡掉了所有基于辅助数组的方案。还有一个容易被忽略的好处这种划分方式不依赖元素值域的有限性。虽然这道题只有0、1、2但三路划分的思路本身可以扩展到任何可比较的数据比如快速排序里的partition变种。从这个角度说你刷这道题学到的skill是可迁移的而不是死记一个解法。3. 三指针核心细节画图拆解3.1 三种情况的处理逻辑为什么长这样这里我用一个例子一步步走一遍。假设输入是[2, 0, 1, 1, 0, 2, 1]初始状态left0cur0right6。第一步cur指向的是nums[0]2触发“遇到2”分支与right6交换数组变成[1, 0, 1, 1, 0, 2, 2]right变成5cur保持0。注意此时cur位置的值是1你不能把cur跳过去因为交换过来的数字还没看过。第二步nums[0]1触发“遇到1”分支cur加1cur1。第三步nums[1]0触发“遇到0”分支与left0交换数组变成[0, 1, 1, 1, 0, 2, 2]left变成1cur变成2。第四步nums[2]1cur变成3。第五步nums[3]1cur变成4。第六步nums[4]0与left1交换数组变成[0, 0, 1, 1, 1, 2, 2]left变成2cur变成5。第七步此时cur5right5循环条件cur right仍然成立。nums[5]2与right5交换自己和自己换right变成4。第八步cur5 right4循环结束。这个例子走完你会发现一个有趣的现象当cur和right交错之后所有元素都已经在正确的位置上了。如果你把交换后cur不加1的逻辑去掉这个例子在第七步会变成cur6然后nums[6]2再交换最终结果虽然可能还是对的但逻辑上已经出现了越界风险。3.2 为什么遇到2时cur不能加1这是三指针解法里最容易被忽略的细节。当你把cur指向的2和right指向的元素交换后cur位置现在是一个“新来的、未被检查过”的元素。如果这个元素是0你必须在当前轮继续处理把它放到左侧如果是1则可以跳过如果是2还得继续交换。所以cur不能盲目加1否则可能把一个0留在右边区域破坏整个分区。我用实际调试中遇到的例子说明输入[1, 2, 0]如果交换2和0后cur直接加1会发生什么初始left0cur0right2。nums[0]1cur加1。此时cur1nums[1]2与right2交换数组变成[1, 0, 2]right变成1。如果此时cur马上加1变成2循环判断cur2 right1直接就停了结果是[1, 0, 2]——完全没排序。这就是错误写法。正确写法中交换后cur不移动下一轮看到nums[1]0与left交换完成排序。这个细节就是“纸上懂了手上一写就错”的最典型陷阱。3.3 循环终止条件的判断很多人写这个题会纠结while条件到底是cur right还是cur right答案是cur right。原因在于当cur和right指向同一个位置时这个位置的值既可能是0、1也可能是2。如果是2你还需要和right交换虽然是自己和自己换然后right减1循环才会终止。如果写成cur right当cur right时循环直接退出那个位置上的2可能没被正确处理或者更准确地说当curright且值为2时右侧区域其实还差这个位置的元素没有被处理结果就错了。举个例子输入[2, 1]left0cur0right1。如果循环条件是cur right第一步cur0指向2和right1交换数组变成[1, 2]cur还是0right变成0然后循环结束。结果是[1, 2]看起来没问题。但换个输入[2, 0]第一步cur0指向2和right1交换数组变成[0, 2]cur变成0right变成0循环结束结果也对。这两个例子都碰巧对了但要构造一个反例很容易。我用[1, 0, 2]测试过错误版初始left0cur0right2。nums[0]1cur加1。此时cur1 right2nums[1]0与left0交换数组变成[0, 1, 2]left1cur2。此时cur2right2cur right不成立循环退出结果恰好正确。但注意此时cur位置的值是2它应该在右侧区域但实际上已经在正确位置上了所以侥幸对了。为了稳妥我建议一律写cur right这是一个边界安全的写法。如果你用cur right能过说明测试数据没踩到边界但面试中万一被构造出特殊用例你就会挂掉。4. 代码实现与逐行逻辑解读4.1 Python 实现与参数选择我把标准实现写出来配合注释逐行解释。def sortColors(nums): # left 指向下一个 0 应该放的位置 # right 指向下一个 2 应该放的位置 # cur 是当前扫描到的位置 left, cur, right 0, 0, len(nums) - 1 while cur right: if nums[cur] 0: # 把 0 换到左侧left 和 cur 都前进 nums[left], nums[cur] nums[cur], nums[left] left 1 cur 1 elif nums[cur] 1: # 1 本来就该在中间直接跳过 cur 1 else: # 把 2 换到右侧right 后退但 cur 不能动 nums[right], nums[cur] nums[cur], nums[right] right - 1 return nums如果你理解了我上一节讲的逻辑这段代码其实不需要背你可以在白板上现场推演出来。每次写这个题我都会在纸上画三个区域左侧是已归位的0中间是未处理的区域右侧是已归位的2。cur就是“未处理区域”的入口left和right分别是两个已归位区域的边界。这样想代码就是你思考过程的直接翻译。4.2 Java 实现要点Java写法和Python几乎一一对应但要注意数组交换不能直接用复合赋值需要中间变量。public void sortColors(int[] nums) { int left 0; int cur 0; int right nums.length - 1; while (cur right) { if (nums[cur] 0) { int temp nums[left]; nums[left] nums[cur]; nums[cur] temp; left; cur; } else if (nums[cur] 1) { cur; } else { int temp nums[right]; nums[right] nums[cur]; nums[cur] temp; right--; } } }我建议你在面试中写Java版本时把交换封装成一个私有方法避免重复写三段swap逻辑同时提升了可读性。但注意如果封装成本地方法注意传入数组的引用类型Java中数组是引用传递修改是生效的。4.3 复杂度计算与证明时间复杂度while循环里每个分支最多执行常数次操作cur或right每次循环都会变化cur加1或者right减1所以整个循环最多执行O(n)轮。每一轮内部操作是O(1)总时间O(n)。空间复杂度所有操作都是原地交换额外变量只有left、cur、right三个指针O(1)空间。这个复杂度是这道题的理论最优。你没法低于O(n)因为必须至少看一眼每个元素才能知道它是什么。你没法低于O(1)空间因为在原地操作的前提下不需要额外空间。所以当面试官问你“还能优化吗”你可以自信地回应在时间和空间两个维度都已经达到最优。写代码的时候永远先画图哪怕只是脑子里画。三步分区问题不画图极易写漏边界条件。5. 实战踩坑那些年我调试过的错误5.1 错误一把0和left交换后cur加多了这是我见过的最高频错误。有些写法会把“遇到0”和“遇到1”的处理合并成if nums[cur] 0: nums[left], nums[cur] nums[cur], nums[left] left 1 cur 1这样写会导致什么问题如果cur位置上交换来的是一个2你直接加1跳过了它后面可能就没有机会再处理这个2了。比如输入[2, 0, 1]初始left0cur0right2。错误版逻辑nums[0]2交换nums[0]和nums[2]数组变成[1, 0, 2]right1cur不加。然后nums[0]1cur加1。然后nums[1]0与left0交换数组变成[0, 1, 2]left1cur2。循环结束结果碰巧对了。但你换个用例[2, 0, 2, 1, 0]这个错误写法就可能出错。所以我的建议是严格按照三种情况分支不要把0和1的判断合到一起保持逻辑清晰。5.2 错误二和right交换时需要交换双方都有意义吗有时候你写交换的代码会担心如果nums[cur]本身就是2、nums[right]也是2交换有没有必要答案是没必要但无害。如果你加一个if判断“只有nums[right]不是2时才交换”会增加分支复杂度而且你需要额外考虑right移动到什么位置才停。最简单的做法就是不判断直接交换right减1虽然多做了些无用的交换操作但代码简洁且正确性容易保证。不过有一个常见的边界问题是当cur和right相等时nums[cur]就是nums[right]自己换自己。这种交换在Python里没问题在Java中也不会有问题就是多一次赋值。真要说效率这点损耗可以忽略。但如果你在面试中有精力也可以加上if (cur right)的判断减少无意义操作。5.3 错误三忘记原地排序直接返回新数组这个错误听起来低级但实际刷题时真的很常见。题目明确要求“原地”修改意味着你不能return sorted(nums)也不能新建一个数组填进去再返回。LeetCode检查的其实是传入数组的内容是否被修改而不是返回值。所以如果你原地修改了numsreturn的时候甚至可以什么都不返回Python默认返回None但为了调试方便返回nums也没有问题。我在刷题的时候习惯写成return nums这是为了自己看得方便但心里要知道核心是把nums数组的内容改对而不是返回一个漂亮的结果。5.4 错误四把循环条件写成 cur n这个错误是另一种思路的误用想从头到尾遍历一遍但没意识到right实际上在从尾部收缩cur最多走到right就应该停。如果你写成cur n就会在已经全部归位之后继续遍历。比如输入[0, 1, 2]left0cur0right2。nums[0]0left1cur1。nums[1]1cur2。此时cur2right2循环继续nums[2]2与right2交换right变成1。接下来cur3如果循环条件是cur n还会继续但cur已经超出数组范围访问直接越界。所以这个写法有数组越界的风险必须用cur right来约束。5.5 常见问题速查表我把调试中遇到的典型问题整理成了一张表刷题前可以扫一眼。典型问题出错的根本原因修正方式遇到2交换后直接跳过新元素没理解交换过来的元素未被检查cur不移动下一轮继续处理循环条件写成cur right边界位置上的2可能没处理改为cur right遇到0交换后left和cur双加1这是正确的但要注意别漏掉等价分支按标准三分支写循环条件写成cur n导致越界未考虑right收缩的影响使用cur right忘记原地修改直接返回新数组误解题目要求在nums上原地赋值或交换遇到1时加1但没考虑交换过来的0不会出现遇到1时没有任何交换保持当前写法6. 从这道题看算法思维的可迁移性6.1 三路划分与三路快排这道题学到的三指针分区思想在快排的三路划分里几乎原样复用。普通快排的partition把数组分为小于pivot和大于pivot两部分但遇到大量重复元素时性能退化严重。三路快排把数组分为小于、等于、大于三部分等于pivot的中间区域不再参与递归特殊情况下性能大幅提升。如果你写过三路快排再看颜色分类会发现只是把pivot换成了固定数字1小于1的就是0大于1的就是2。算法骨架完全一样。所以做这道题的时候建议你顺手把三路快排也写一遍巩固这个思维。6.2 双指针的“相遇”逻辑适用范围三指针其实是从双指针发展出来的。在很多数组题里双指针都是从两端向中间扫描比如两数之和II、盛最多水的容器。这道题在双指针基础上多了一个cur用来遍历中间未处理区域“相遇”的逻辑就从“left和right相遇”扩展成了“cur越过right”。理解了这个递进关系以后遇到“数组分区”“奇偶排序”“移动零”这类题你都能看出它们的共性。移动零那道题其实就是颜色分类的退化版只有0和非0两类一个指针维护0的边界一个指针遍历即可。这验证了一个规律算法题不靠背靠理解底层模式见过一道经典题等于见过一类题。6.3 面试中如何讲这道题如果你在面试中被问到这道题建议按照这个顺序讲第一步明确题目约束原地方案、常数额外空间。 第二步从最朴素的计数排序讲起分析它为什么不是最优两趟扫描。 第三步提出三指针方案画图解释三个指针的职责。 第四步强调遇到2时cur不移动的原因。 第五步口述复杂度O(n)和O(1)。我面试别人的时候最看重的不是候选人能不能默写出代码而是能不能把“遇到2时cur为什么不加1”讲清楚。这个细节几乎能过滤掉一半只是背过答案的人。所以如果你能把第3节的内容吃透面试的沟通环节基本稳了。7. 刷题方法论如何从这道题举一反三7.1 同类题对比练习清单刷完颜色分类我建议你马上做几道关联题检验自己是不是真的掌握了“指针分区”这一招第一道是“移动零”要求把数组中的0移动到末尾保持非零元素相对顺序。这题把颜色分类的“0区”和“非0区”分离只需要一个指针维护0的边界另一个指针遍历。如果你能快速写出来说明你对“边界指针”的维护已经有感觉。第二道是“移除元素”给你一个数组和一个值val让你原地移除所有等于val的元素。这题同样用双指针一个慢指针维护“非val区间”的末尾一个快指针遍历。跟颜色分类的left和cur的分工非常相似。第三道是“奇偶排序”让你把数组中的奇数放在偶数前面。这个就是二分类版的颜色分类用两个指针或者一个边界指针都能解决。练习的时候我建议你先别看题解自己用“一个边界指针 遍历指针”的通用模板去套套不出来的地方再翻题解。7.2 一个通用的“K区域划分”模板如果你把颜色分类的三指针抽象一步其实可以写出一个通用的K区域划分模板用K-1个边界指针划分K个区域遍历指针cur从左到右扫描根据当前元素属于哪个区域与对应的边界指针交换并移动指针。举个例子假设值域是[0, K-1]要原地排序成升序你可以用K-1个指针分别指向每个元素的边界。但实际写起来只有当K很小的时候才值得这么做。K3是这道题K2是移动零K4及以上通常计数排序更简单。这也是为什么经典题选择“0、1、2”作为值域刚好卡在“指针划分仍然简洁”的临界点。7.3 我在刷题中的两个小习惯第一个习惯每道题写完之后随机生成大量测试用例暴力法对照验证。比如颜色分类你可以用Python的random生成若干个只含0、1、2的数组同时用标准库sorted算一个基准答案再和自己写的sortColors对比。这样做几次边界问题基本都能暴露出来。import random for _ in range(10000): arr [random.randint(0, 2) for _ in range(random.randint(0, 20))] expected sorted(arr) sortColors(arr) if arr ! expected: print(出错了:, arr) break else: print(全部通过)这个随机测试的脚本我几乎每道数组题都会用比只看示例用例可靠得多。你可以把这个当成自己刷题的标配工具。第二个习惯写题解或笔记时不用代码块保存完整解析而是只记录“卡住我的那个点”。比如对这道题我只记了一句——“遇到2交换后cur别动等下一轮检查”。下次回看笔记一眼就能回忆起核心坑点效率远高于重新读一遍长篇大论。实际刷题下来我的体会是这道题值得反复写几遍不是为了背答案而是每次写都能加深对“边界条件”和“指针移动时机”的理解。你把这个过程走扎实后面遇到更复杂的双指针题会轻松很多。