初次看到“颜色分类”这道题时很多人会觉得它就是一个普通的排序问题无非是[0,1,2]三种数字排个序而已。但真正动手刷过力扣Hot 100的朋友应该都知道这题在面试里出现频率极高考察的绝不是“会不会调sort()”而是你对数组原地操作、双指针边界控制、以及循环不变量这类基本功的理解深度。网络上经常把这题称为“荷兰国旗问题”我第一次看到这个名字时还愣了一下后来才明白它源自计算机科学里一个经典的抽象问题把一堆红色、白色、蓝色三种颜色的球按颜色顺序排列好。这篇文章我会把75题从题目本质、解法演进到三种核心写法的优缺点和边界细节再到我实际刷题时踩过的一些坑全部掰开揉碎讲一遍。不管是刚入门想要弄懂双指针的新手还是准备面试想快速过一遍经典题的进阶读者都能从中拿到可以直接上手的结论和代码。1. 题目解读与核心考点1.1 题目描述还原先看一眼题目的原始描述我按记忆还原保证不偏离原题语义给定一个包含红色、白色、蓝色一共 n 个元素的数组nums原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。这里用整数0、1、2分别表示红色、白色、蓝色。题目要求不使用库内置的sort函数且需要原地排序。举个简单例子输入nums [2,0,2,1,1,0]期望输出[0,0,1,1,2,2]。从数据结构视角看这其实就是一个只包含三种键值的数组排序问题但它有一个非常醒目的约束——“原地”这意味着不能开额外数组、不能轻松地用空间换时间。1.2 为什么被称为“荷兰国旗问题”这个问题的英文名字是“Dutch National Flag Problem”最早由计算机科学家提出。荷兰国旗恰好是三条色带红色、白色、蓝色从上到下顺序排列。这题的抽象模型就是给定一堆分别涂成红、白、蓝的球乱序放在数组里现在要将它们按国旗颜色顺序重新排列。这个经典模型的特殊之处在于元素种类固定只有三种可预先知道所有可能出现的取值这就给“一趟扫描解决”埋下了伏笔。之所以面试官偏爱这题是因为它考察的并不是“你知不知道某个冷门算法”而是你在面对一个有明确分类边界的数组时能不能想到用两个指针把数组分成三个区间。这种“分区”思想恰恰是快速排序、三路快排、滑动窗口等高级算法的基础。1.3 隐藏在题目背后的考点清单很多人以为这题考点只有“双指针”其实它至少覆盖了以下四个层面的东西原地操作能力是否能够做到空间复杂度O(1)不借助额外数组。对单趟遍历的理解最优解要求时间复杂度O(n)并且只需要一次遍历。遍历过程中还需要持续性维护某个“区间不变式”。边界条件的敏感度左右指针移动的时机、何时跳出循环、遇到当前值属于哪个区间时该做什么操作——这些细节决定了代码是否会出现死循环或越界。对循环不变量的表述能力面试时面试官常常会追问“你能解释一下为什么这个解法是正确的”这需要你清楚地描述三个区间各自的Index范围。2. 从暴力到双指针的解法演进2.1 直接调用内置排序最省事却不是考点如果你在笔试环节先用Arrays.sort(nums)蒙混过关那确实能通过所有测试用例因为[0,1,2]本身就是可比较的整数。但这在面试中是绝对要避免的因为题目已经明确“不使用库内置的sort函数”甚至面试官看到这种写法会直接判定你对“原地”和“算法复杂度”缺乏敏感度。从复杂度角度说内置排序通常是快排或双轴快排平均时间复杂度O(n log n)但如果你在面试中回答“可以调用排序”就会暴露你完全没意识到“键值种类只有三种”这个信息量巨大的前提。理论上三路划分完全可以把时间复杂度压到O(n)。这就像明明可以在一堆只包含红、白、蓝三种颜色的球里用“看一眼就分区”的方式整理完毕你却非要拿起一套通用排序算法把所有球按某种规则逐一比较。方向对但严重浪费题目提供的已知条件。2.2 两趟扫描计数排序思路的自然延伸最容易想到的原地思路是既然这个数组只包含0、1、2那我先扫一遍统计0、1、2各自的数量再根据数量把对应的值重新填回去。具体做法是第一趟遍历数组统计count[0]、count[1]、count[2]。第二趟按顺序填充前count[0]个位置填0接着count[1]个位置填1剩余位置填2。这种写法的复杂度是时间复杂度O(n)空间复杂度O(1)——因为计数只需要三个变量不需要额外数组。它完全符合题目要求逻辑也极其简单基本不会出错。但它的缺点是“两趟扫描”本质上是一种计数排序思想的简化版。面试中你提出来作为第一步是完全可以的能体现你有思路然后进一步优化成单趟扫描就更完美了。2.3 一趟扫描双指针的经典解法这道题真正让人拍案叫绝的解法是用两个指针p0和p2分别指向“下一个0应该在的位置”和“下一个2应该在的位置”。核心思路是左指针p0初始指向数组开头维护的是“已排好的0区间”的右边界。右指针p2初始指向数组末尾维护的是“已排好的2区间”的左边界。用第三个指针i从头到尾遍历数组遇到0就把它放到左边遇到2就把它放到右边遇到1就跳过继续前进。这里的关键在于因为0和2的最终位置都被指针锁死了中间自然剩下的区域就全部是1。这比“两趟扫描”更进了一步——你只用一个循环就完成了分区的全部工作。为什么要追求“一趟”因为这在某些严格的实时场景有性能意义更关键的是单趟遍历的过程本身就是“一边扫描一边整理”相当于一次手工分拣它的思维模式能够迁移到很多其他问题上。2.4 边界条件与循环不变量理解双指针写法前必须先建立“循环不变量”的概念在某一次循环开始前数组被三个指针分成几个区间并始终保持以下性质[0, p0)区间内所有元素都是0。[p0, i)区间内所有元素都是1。[i, p2]区间内是尚未扫描的元素。(p2, n-1]区间内所有元素都是2。也就是说我们每处理一个当前元素nums[i]都要维持这四个区间的划分正确性。明白这个不变量就不会写错交换后的指针移动逻辑。很多人写这一题时总是纠结“交换之后i要不要”本质上就是对“当前指针指向的是已扫描还是未扫描元素”没有想清楚。3. 三种核心解法的完整实现与逐行解析3.1 方案A内置排序仅用于笔试备选虽然不推荐但为了完整性我先把最直白的写法贴出来import java.util.Arrays; public class Solution { public void sortColors(int[] nums) { Arrays.sort(nums); } }这段代码优点是零思考、零出错率、系统排序算法在大部分情况下性能极佳。缺点是完全无法体现你对这道题特殊结构的理解。如果你是在牛客/力扣在线笔试中遇到这题且时间非常紧张那么用它会比手撕一个出错的快排要稳妥。但面试官面前慎用一旦对方要求“不要用排序库”就得拿出真正的双指针方案。3.2 方案B两趟计数扫描最直观、最不易错public class Solution { public void sortColors(int[] nums) { int count0 0, count1 0, count2 0; // 第一趟统计 for (int num : nums) { if (num 0) count0; else if (num 1) count1; else count2; } // 第二趟回填 int idx 0; while (count0-- 0) nums[idx] 0; while (count1-- 0) nums[idx] 1; while (count2-- 0) nums[idx] 2; } }这个解法最容易理解把问题分成“统计”和“写入”两个阶段。count0、count1、count2的统计不需要数组用三个变量即可空间复杂度确确实实是O(1)。回填时严格按照0、1、2的顺序填充重复赋值多少遍都不影响正确性因为后面覆盖的就是前面的空位。这个写法最大的价值是在自己思路混乱时作为保底方案。即便面试官要求优化到单趟你也能以此作为垫脚石引出下面的双指针。3.3 方案C单趟双指针扫描最优解这是面试中最值得掌握的写法我给出三个主流语言的版本并逐行解释关键逻辑。Java版本public class Solution { public void sortColors(int[] nums) { int p0 0; // 下一个0放置的位置 int p2 nums.length - 1; // 下一个2放置的位置 int i 0; while (i p2) { if (nums[i] 0) { // 将0换到前面 swap(nums, p0, i); p0; i; } else if (nums[i] 2) { // 将2换到后面 swap(nums, p2, i); p2--; // 注意这里没有i因为换过来的元素可能是0或1需要重新判断 } else { // 当前是1直接跳过 i; } } } private void swap(int[] nums, int a, int b) { int temp nums[a]; nums[a] nums[b]; nums[b] temp; } }Python版本class Solution: def sortColors(self, nums: List[int]) - None: Do not return anything, modify nums in-place instead. p0, p2, i 0, len(nums) - 1, 0 while i p2: if nums[i] 0: nums[p0], nums[i] nums[i], nums[p0] p0 1 i 1 elif nums[i] 2: nums[p2], nums[i] nums[i], nums[p2] p2 - 1 else: i 1C版本class Solution { public: void sortColors(vectorint nums) { int p0 0, p2 nums.size() - 1, i 0; while (i p2) { if (nums[i] 0) { swap(nums[p0], nums[i]); p0; i; } else if (nums[i] 2) { swap(nums[p2], nums[i]); p2--; } else { i; } } } };关键逻辑逐行拆解重点解释两个最容易让人卡住的地方第一为什么nums[i] 0时交换后要i因为p0始终指向的是已排好的0区间后的第一个位置它指向的元素要么是1要么就是当前i位置本身。也就是说从p0交换过来的值已经被扫描过或者恰好是nums[i]自己不可能是一个未处理的2。因此交换后可以放心让指针前进。第二为什么nums[i] 2时交换后不能i因为p2指向的是未扫描区域的末尾前的边界。将i位置的2交换到后面后从后面换过来的元素是什么我们完全不知道它可能是0、1、2任意一种。如果直接跳过这个换过来的值就被遗漏了可能会破坏整个排序结果。所以此时只能缩小p2而i原地不动继续判断换过来的新元素。3.4 代码的性能对比与选择建议方案时间复杂度空间复杂度遍历次数适用场景内置排序O(n log n)O(1)或O(n)1次内部笔试保底两趟计数O(n)O(1)2次面试初答单趟双指针O(n)O(1)1次最优方案如果你的目标是把这题彻底弄懂那我建议你从两趟计数开始理解基数统计的核心再升级到单趟双指针。不要直接背代码。你要背的是“为什么在遇到2时不前进i”这个决策逻辑以及“循环不变量”如何保证正确性。面试时通常你抛出一个“我能做到一趟扫描解决”的信号面试官眼睛就会亮起来接下来其实就是考察你能否把边界处理清楚。4. 常见错误与排查思路实录4.1 死循环把nums[i] 2的分支也写成i这是我见过最多的错误写法新手很容易照着nums[i] 0的模式写给2的分支也加上了i结果一跑就超时。原因前面已经说透交换过来的元素是未知的如果直接前进就会漏掉。如果你写完代码后出现超时优先检查2分支是否有i。排查时可以在循环体开头打印i、p0、p2的值你会发现交换两次后i的数值没有变大始终在原地处理新来的与2重复交换——这时候就需要清醒认识到这是漏掉了对新元素的处理。4.2 当nums[i] 0时交换后不移动i会怎样有些读者会困惑那0分支为什么我改成“只p0不i”也能通过部分用例其实这是隐藏的bug。因为从p0位置交换过来的可能是1不前进会导致这个1再次被当作当前元素审视。虽然下一轮循环时这个1会被识别为1然后i逻辑上似乎也能继续推进但仔细想这会造成多余的交换轮次。更严重的是万一p0指向的位置恰好是i本身比如数组原本开头就有0交换后i不动但p0已经增大了下一次循环又走到同一个位置这个位置的值仍然是0交换后无变化继续原地卡住直到循环条件不满足不会因为p0 i后交换会反复发生在已排好的0区间内导致某种形式的重复处理结果可能依然是正确的但非常冗余。正确的做法是记住0分支交换后i这是保持“循环不变量”的重要一步。4.3 左指针p0和扫描指针i重叠时的问题当p0和i指向同一个位置且值为0时交换自身等于没交换然后p0、i一起推进——没有任何问题。但当p0和i指向同一位置且值为1时直接走else分支i推进——也没问题。真正复杂的是当p2小于i时循环是否继续。循环条件是while (i p2)这意味着一旦i跨过了右边界p2就说明未扫描区域已经空了。为什么不是i nums.length因为p2右侧已经全是2扫描它们没有意义还可能导致越界或多余交换。这是很多人在写循环终止条件时容易疑惑的地方。其实只要画出三个区间你一眼就能确定终止条件中间“未扫描区间”为空时立即停止即i走到p2右边。4.4 两趟计数方案的内存陷阱两趟扫描方案虽然直观但如果你写成了用HashMap或者长度为3的数组来统计也不算错。但面试官可能会追问“能否不使用额外数组”这时你要意识到因为只有三种值用三个整型变量就是最精简的O(1)空间。还有一个细节统计时必须用else if而不是三个独立的if否则会重复计数。我第一次手写时因为顺手用了两个if把1和2的统计都算乱了测试直接红了一大片。这种低级错误在紧张状态下很容易犯建议写完后用例[1,2,0]快速手推一遍第一趟得到count01, count11, count21第二趟填[0,1,2]完全正确。4.5 面试追问为什么不用快排的三路分区其实这题和快排的三路划分3-way partition本质上是一模一样的思想。[0, p0)、[p0, i)、[i, p2]、(p2, n-1)这四个区间恰好对应三路快排中“小于基准值、等于基准值、大于基准值”的三个区间。面试时如果你能主动提一句“这本质上是三路快排的简化版基准值是1”会显得你对排序算法的融会贯通程度更高。这也是为什么这题被放进Hot 100的原因之一它不只是一个独立的练习题更是后续理解快速排序优化版比如处理大量重复元素的三路快排的重要基石。5. 实操心得与扩展思考5.1 刷题时的最佳练习路径我个人的建议是拿到这题后按下面这个顺序练习每一层都有不同的收获第一轮直接写两趟计数跑通所有用例确保对“原地、O(1)空间”有基本体感。这一轮能够让你理解“统计回填”是解决有限取值数组的通用套路。第二轮不看任何题解自己画数组区间图推导双指针。建议在纸上画一个长度为8的随机数组用三个指针模拟每一步的交换过程直到你能把“为什么遇到2不前进i”讲得清清楚楚。第三轮分别用Java、Python、C各写一遍感受语言差异对实现的影响。尤其是Python的多元赋值交换写起来非常简洁但要注意nums[p0], nums[i]交换时如果两者指向同一个位置Python的元组赋值也能正确执行无须担心。第四轮限时5分钟写一遍模拟面试手感。写完后再口述一遍循环不变量。如果能在安静状态下5分钟之内流畅写完并解释清楚这题基本就拿下了。5.2 从颜色分类延伸出的算法谱系弄懂这题后可以尝试把它们串成一条知识链。最直接相关的是三路快排你完全可以把sortColors的代码改成“对任意基准值pivot做三路划分”的模板只把判断条件从0、2改成 pivot、 pivot。再往前一步滑动窗口类问题也依赖类似的区间维护思想只不过窗口的伸缩逻辑更复杂。最后如果数组不是三种颜色而是K种颜色那就是另一个经典问题“按颜色分组”此时可以递归地做颜色分区或者用桶排序的思想但复杂度会相应提升。理解这一题能让你对这整条算法谱系的领悟都上一个台阶。5.3 一个细节为什么题目叫“颜色分类”而不是“排序”说来有意思这道题官方叫“颜色分类”因为它在现实中的直接映射就是“将一堆彩色物体按颜色排好”。但它的本质确实就是排序。命名上的差异提醒我们算法题很多时候披着应用的外衣核心还是数据结构与指针操作。阅读题目时不要被“颜色”这种具象名词迷惑要立刻抽取出“数组、三种取值、原地、排序”这些核心约束。我在带人刷题时经常强调一句话拿到算法题的第一步不是想解法而是把题目的约束条件全部列出来然后思考每个约束条件在逼你放弃哪些已知解法。比如“原地”逼你放弃“新建数组再填回去”“不用库排序”逼你放弃Arrays.sort“只有三种值”暗示你可以利用值域有限来做线性扫描。5.4 常见在线评测的边界用例使用力扣自测时有几个用例值得反复跑[]空数组应当直接结束不越界。[0]单个元素p0、p2、i三个指针应当正确处理。[2,0,1]这是最容易出错的组合手动推一遍你就知道为什么。[2,0,2,1,1,0]官方案例测试基本覆盖所有交换类型。[0,0,0,0]全是0的情况下循环条件i p2如何退出值得观察。针对空数组情况p2 len(nums) - 1 -1此时while(i p2)条件为0 -1为假直接退出没有任何问题。针对[2,0,1]手动推演一下初始p00, p22, i0nums[0]2交换nums[2]和nums[0]数组变成[1,0,2]p21i0不变下一轮nums[0]1i变成1下一轮i1此时nums[1]0交换nums[0]与nums[1]数组变成[0,1,2]p01i2此时i2 p21循环退出。结果是正确的且整个过程非常清晰。5.5 我个人的总结体会我在实际刷题和面试候选人过程中发现能写出双指针解法的人不少但能把“为什么2分支不移动i”讲清楚的人不到一半。这提示了一个深层问题很多人背下了代码模式却没有真正建立“区间划分”的mental model。所以我特别建议画图把数组想象成一条从左到右的传送带左边已经整理好的0区右边已经整理好的2区中间是待处理的未知区域。你手里拿着一个指针i从传送带左端往右走遇到0就扔到左边已整理区遇到2就扔到右边已整理区遇到1就跳过。右边扔过来的是什么你不知道所以得停下来再看一眼。这么一想整个代码逻辑就非常顺了。这也是我想留给你的一句话刷题不是为了记住“这道题怎么写”而是为了形成一套“遇到分类问题如何划分区间”的思考方式。有了这套思考方式别说这题三路快排、滑动窗口、颜色分组你都再也不会怕了。