LeetCode热题100做到第93题这题叫颜色分类。最近在整理刷题笔记时我发现身边不少刷题的人都在三指针这种“看起来简单、写起来翻车”的题目上吃过亏今天就把这道经典题掰开揉碎聊一聊。它要解决的问题很明确一个只包含 0、1、2 的数组要求原地排序成 0 在前、1 在中间、2 在后的顺序不能用内置 sort空间尽量 O(1)。题目虽短背后是荷兰国旗算法、循环不变量、双指针边界处理这些硬核考点刷明白这一道很多同类问题都能迎刃而解。适合正在刷 LeetCode 热题100 的、准备面试的、或者想补一补算法基础的读者不需要太高门槛看完就能上手写代码。1. 题目到底在考什么1.1 原题描述与输入输出LeetCode 上的颜色分类英文名叫 Sort Colors在 LeetCode 热题100 中属于“技巧”类的题目。题目给一个长度为 n 的数组里面的元素只能是 0、1、2分别对应红、白、蓝三种颜色。要求原地对它们排序让所有 0 排在前面所有 1 排在中间所有 2 排在最后面。这里的“原地”意味着不能额外开一个新数组再拷贝回去只能在原数组上通过交换或覆盖完成排序。原题还特别强调不要使用库里的 sort 函数。这就把很多人的“排序题直接调 sort”的偷懒路堵死了。示例部分很简单比如输入[2,0,2,1,1,0]输出是[0,0,1,1,2,2]输入[2,0,1]正确的输出是[0,1,2]这里估计会有同学第一反应去交换 1 和 2其实不用那么麻烦0 全部到左边、2 全部到右边1 自然就在中间。写题的时候要自己把输出写对别小看这个细节很多人提交报错就是栽在测试用例理解上。再看一下约束条件n 的范围是 1 到 300数组规模不大。但算法题不因为你数据小就降低标准O(n) 时间、O(1) 空间依然是有要求的。所以这道题虽然输入简单但考察点非常集中原地修改、一趟扫描、常数空间。很多人在 LeetCode 上刷到这道题第一眼觉得“这不是排个序吗”然后迅速被三指针的边界问题折磨一遍说到底还是没有看清楚题目真正要考的东西。1.2 为什么这题被放进热题100热题100选题目不是只看难度更看考点价值。颜色分类只是一个中等题但它同时覆盖了“原地修改数组”“双指针/三指针设计”“循环不变量分析”这三件事。这三件事在面试算法题里出现频率极高尤其是双指针它从数组题一路延伸到链表题、字符串题几乎每种题型都能见到。而且这道题表面上叫“分类”听上去像排序实际上考的不是比较排序而是 partition划分思想这是快速排序的核心也是荷兰国旗问题最经典的入门载体。从刷题阶段来看做到热题100的第93题说明大部分人已经具备一定基础了。这时候需要的不再是单纯记住某个数据结构而是能对一道简单描述做出多维度的思考能不能一趟遍历能不能常数空间能不能处理扩展颜色分类恰好把这些问题全部塞进去。所以它出现在热题里一点都不奇怪面试官也喜欢拿这种“短小精悍”的题考察候选人写代码的严谨度。再补充一点很多公司的面试题会把这题稍微变形比如把 0/1/2 改成“负数/零/正数”本质一模一样。你要是只会背答案换个皮就容易愣住但如果你理解了三指针的循环不变量换多少层皮都能秒杀掉。这也是我强烈建议把这道题吃透的原因。热题100刷到后期你会发现题目之间经常共用一套模型颜色分类就是其中一个非常典型的“母题”。2. 从暴力解法到计数排序2.1 最容易想到的方案先数颜色再回填拿到这道题第一反应通常不是三指针而是“数一下每个数字出现几次再重新填进去”。这个思路非常直观也完全能通过 LeetCode 的测试用例。做法是开一个长度为 3 的计数数组 counter第一遍遍历统计 0、1、2 的个数第二遍遍历数组根据 counter[0] 个 0 填到最前面counter[1] 个 1 填中间counter[2] 个 2 填最后。代码大概长这样def sortColors(nums): cnt [0, 0, 0] for x in nums: cnt[x] 1 i 0 for color in range(3): for _ in range(cnt[color]): nums[i] color i 1这个方案时间复杂度是 O(n)空间呢注意这里的 cnt 长度固定为 3不随 n 变化所以可以认为空间复杂度是 O(1)。很多同学写到这里就满足了提交也能过毕竟题目确实没有明确禁止“先统计再填充”。但从学习角度这条路只能算是“入门题解”不是最优解因为它把数组扫了两遍而且没有体现任何指针技巧。尤其当你以后遇到变体题比如“负数、零、正数”三分区计数排序的思路依然能用但面试官想要的显然不是这个。2.2 计数排序方案的两大局限计数排序在这里的局限主要有两个。第一个是扫描次数。题目没有明确要求一遍扫描但如果你去面试面试官十有八九会追问“能不能只遍历一遍”因为真正考察的点不是你会不会统计频次而是你能不能用一个指针在遍历过程中就把数组分好区。第二个局限是可扩展性差。如果把颜色从 3 种变成 K 种计数数组就要开 K 个位置空间复杂度变成 O(K)。当 K 很大比如元素取值范围覆盖整个 int 时计数排序的直接思路就不太现实了虽然你可以用哈希表做压缩但耗费的开销也不小。所以计数排序更适合“元素种类固定且较小”的场景。在这道题里因为只有 3 种颜色它其实是一个合法解但作为一个刷题人不能满足于“能过就行”。热题100里的中等题你要的是“这道题的所有解法都能说出来并且能解释清楚优劣”不然面试时一道题就能暴露深度。我自己刷题的习惯是先写一个最容易想到的版本确认能 AC 之后继续问自己“能不能更好”直到想不出来为止。颜色分类就是一个典型例子暴力解和最优解之间隔着一层窗户纸但捅破这层纸你的算法理解会上一个台阶。为了更直观地对比各种方案的差异列一个表方案时间复杂度空间复杂度遍历次数是否原地调用内置 sortO(n log n)O(1)一次是但题目禁止计数排序回填O(n)O(1)两遍是三指针荷兰国旗O(n)O(1)一遍是看这张表就知道三指针在数据规模上不一定比计数排序快多少但“一遍扫描”这个性质在面试中是很大的加分项因为这说明你能在遍历过程中动态维护状态而不是依赖全局统计。2.3 为什么面试官会追问“能不能一趟扫描”一趟扫描意味着在遍历数组的过程中每个位置的信息只处理一次或者交换后需要重新审视时也属于常数次不依赖第二遍统计。它要求的是一种“动态分区”的能力数组从左到右被切成几段每一段代表一类数据指针向前移动时不断将当前元素丢到正确的区域里。这种能力在快速排序的 partition、荷兰国旗问题、奇偶分类、链表 partition 中都通用。一旦掌握了后续写快排的“三路切分”也能顺手很多。所以面试官追问一趟扫描本质上是想看你能不能从“排序”的思维切换到“划分”的思维。排序关心的是全局顺序而划分只关心满足某个谓词的数据落在哪一侧。颜色分类只要 0 在左、2 在右1 自然就在中间本质上就是一个三分区问题根本不需要做完整排序。理解到这个层面三指针解法就是水到渠成。这也是为什么我不建议一上来就背三指针代码而是先想清楚这个问题和“排序”两个字关系不大它是一个“分类”问题。3. 正解荷兰国旗三指针算法3.1 荷兰国旗问题的由来颜色分类这题还有一个更广为人知的名字荷兰国旗问题Dutch National Flag Problem。它最早由计算机科学家 Edsger Dijkstra 提出问题描述是用红、白、蓝三色旗子按顺序排列对应到编程里就是把一个只包含三种值的数组原地重排成三段。Dijkstra 本人也是快速排序和其他很多经典算法的提出者之一他拿这个问题来讲“循环不变量”和“有限状态变化”非常合适。为什么叫“荷兰国旗”因为荷兰国旗正好是红、白、蓝三条横带和题目中的三色划分刚好对应。这个命名虽然有点历史但你现在去查资料依然能看到很多算法教材直接把它叫作 Dutch National Flag。大家在题解里看到“DNF”缩写要知道说的就是这道题。算法题有好多别名比如“移动零”其实就是简化版荷兰国旗只分两类。搞清这些别名刷题时搜索资料会方便得多也方便你跟同行交流。3.2 三个指针到底在维护什么荷兰国旗算法的核心是维护三个区间用三个指针把它们隔开。我们令数组下标从 0 开始设置 p0 指向“下一个 0 应该放的位置”p2 指向“下一个 2 应该放的位置”i 表示当前正在扫描的位置。整个数组被分成四段[0, p0)区间全部是 0已经归位。[p0, i)区间全部是 1已经归位。[i, p2]区间还没扫描的元素全部未知。(p2, len-1]区间全部是 2已经归位。这三个区间加在一起就是整个数组。你会发现指针 p0 是 0 区间的右边界i 是 1 区间的右边界p2 是 2 区间的左边界。扫描过程中我们不断从未知区取出一个元素 nums[i]如果它是 0就把它放到 p0 的位置p0 右移一位同时 i 也右移一位因为换过来的一定是 1不需要再检查。如果它是 2就把它放到 p2 的位置p2 左移一位但 i 不能动因为从右边换过来的元素是未知的要继续检查。如果它是 1那它本来就该留在中间区直接 i。这个循环的终止条件是 i p2也就是未知区间被扫描完。整个过程每个元素最多被交换两次所以时间是 O(n)空间只需要三个指针O(1)。理解这三个区间的意义是写出正确代码的前提。如果你只是机械地记忆“遇到 0 就交换 p0遇到 2 就交换 p2”很容易在边界条件上出错因为你不清楚每一步交换之后各个区间到底发生了什么变化。3.3 完整代码与逐行解读Python 的完整实现非常短建议背下来之后再用自己的话讲清楚class Solution: def sortColors(self, nums: List[int]) - None: n len(nums) p0, p2 0, n - 1 i 0 while i p2: if nums[i] 0: nums[i], nums[p0] nums[p0], nums[i] p0 1 i 1 elif nums[i] 2: nums[i], nums[p2] nums[p2], nums[i] p2 - 1 else: i 1逐行看n 是数组长度p0 和 p2 分别指向左右边界i 从 0 开始。while i p2 表示只要还有未知元素就继续。遇到 0与 nums[p0] 交换交换后 p0 位置确定是 0所以 p0 前移同时因为从 p0 换过来的一定是 1所以 i 也可以前移。遇到 2与 nums[p2] 交换交换后 p2 位置确定是 2所以 p2 后移但换到 i 位置的元素来自未知区可能是 0、1、2所以 i 不动。遇到 1什么都不用交换直接前进。这个代码用原地交换完成排序所以不需要额外开辟数组LeetCode 会检查 nums 是否被原地修改因此也不需要有返回值。我写 C 或 Java 时逻辑完全相同只是交换写法麻烦一点比如 C 里用std::swapJava 里写临时变量核心思想完全一致。如果你是刚接触这道题建议把代码背下来之后再用自己的话讲一遍讲得清楚才说明真的懂了。3.4 几个容易写错的细节三指针算法虽然代码短但写错概率不低。第一个常见错误用for i in range(n)代替 while。如果你在遇到 2 时不处理 i 递增for 循环会在下一轮自动加 1导致刚从右边换过来的元素没被检查排序结果错误。所以除非你在循环体里手动控制 i否则一定要用 while。第二个常见错误循环条件写成i n。当 i 超过 p2 后右边全是 2继续处理会把已经排好的 2 又换回去。所以终止条件必须是i p2。第三个常见错误遇到 0 时交换后只 p0 忘记 i或者遇到 2 时交换后忘了 p2--。这些都是细节但造成的后果很直观。还有一个值得展开的地方为什么遇到 0 时交换后 i 可以放心加 1假设当前 i 已经大于 p0这是常态那么[p0, i)这个区间里应该全部是 1。因为 p0 指向的正是第一个 1所以 nums[p0] 的值必然是 1。当 nums[i] 0 时把 p0 位置的 1 换到 i 位置i 位置就变成 1 了属于中间区可以直接前进。如果 p0 i交换的是自己原本就是 0但交换后 i 位置确实是 0同时 p0 加 1 后0 区向右扩展i 加 1 也合理。所以两种情况都支持 i。而遇到 2 时从 p2 换过来的元素可能来自未知区中的任意值不能做任何假设所以 i 必须停留一次重新判断。我自己的习惯是写完代码后马上自己走一遍小数组比如[1,2,0]看看 i、p0、p2 每一步怎么变。手动跑通一遍对理解循环不变量帮助特别大。后面会在刷题现场部分再带大家完整模拟一遍。4. 刷题现场从读题到AC的完整复盘4.1 我的第一反应与思路调整我把这个标题挂在热题100刷到第93题当时脑子里冒出三个方案。第一个是直接调用 sort()一看题目禁止pass。第二个就是计数排序写了十几秒提交能过但我又跟自己说如果这是面试题面试官肯定要追问索性直接想更优的。第三个是回忆起荷兰国旗问题三指针在一趟扫描里完成分区。于是我开始在白板上画数组把 0 区、1 区、未知区、2 区画出来再填指针。这种“多方案对比”的过程其实很推荐。刷题不是追求一次通过而是要把一道题的思考链条完整走一遍。很多读者私信问我怎么刷 LeetCode 热题100我的回答永远是先把题目读透再想暴力解法再优化复杂度最后找相似题归类。颜色分类这道题非常适合做这种训练的样本因为它的暴力解和最优解差别清晰复杂度分析也简单。你甚至可以把它当成一个“从排序到分区”的思维转折点以前你看到乱序数组想到的是排序算法以后你还会想到 partition这两种思维差异会直接影响你解难题的速度。4.2 手动模拟一个关键用例拿一个容易出错的用例[2, 0, 1]来模拟。初始i0, p00, p22。第一步nums[0]2是 2交换 nums[0] 和 nums[2]数组变成[1,0,2]p21i 仍然 0。此时循环条件 0 1 成立。nums[0]1是 1直接 i1。此时 i1, p21循环继续。nums[1]0是 0交换 nums[1] 和 nums[p00]数组变成[0,1,2]p01i2。循环条件 2 1 不成立结束。这个模拟过程很直观地展示了为什么遇到 2 时 i 不能立刻加 1因为第一次交换后从右边换来的数是 1需要留在位置 0 继续检查如果当时 i 加 11 就会跑到已经扫描过的位置最终数组会变成[1,0,2]之类的错误结果。能把这个例子讲给别人听说明你真的理解了算法。我们再试一个常见边界[2,2,1]。初始 i0,p00,p22。nums[0]2交换 nums[0] 和 nums[2]得[1,2,2]p21i0。nums[0]1i1。此时 i1,p21nums[1]2交换 nums[1] 和 nums[1]自己换自己p20i 仍 1。循环结束结果是[1,2,2]。这里可以看到 p2 已经小于 i右边区间为空空操作一次也不会出错。很多同学害怕自己交换自己其实没问题反而说明边界处理得很干净。4.3 自测用例清单刷题时我会准备一组覆盖边界情况的用例不只依赖示例。颜色分类我建议至少跑这几种普通混合[2,0,2,1,1,0]-[0,0,1,1,2,2]逆序[2,1,0]-[0,1,2]全是同一种颜色[1,1,1]-[1,1,1]只有两种颜色[2,0]-[0,2]单元素[0]-[0]极端分布[2,2,0,0]-[0,0,2,2]把这些用例在本地跑一遍基本能覆盖所有边界。如果是 LeetCode 上提交我还会把数组长度很小时的所有排列组合都生成出来写一个全排列测试脚本用三指针结果和计数排序结果对比。这个习惯帮我抓出过不少“自认为正确”的代码。很多同学刷题只依赖题目给的示例这其实不够题目示例往往不够极端一个边界用例可能就暴露问题。4.4 面试时如何讲出加分点如果你在面试中碰到这题不要上来就闷头写代码。先跟面试官确认输入范围和空间要求然后说出你的思考路径“这题可以用计数排序时间 O(n) 空间 O(1)但需要扫描两遍如果要求一趟扫描可以用三指针模拟荷兰国旗分区。”一句话就能让面试官知道你不只会背答案。写代码时在关键判断旁简单说出理由比如遇到 2 时 i 不涨是因为右边换来的数没看过。写完后主动提出跑一个边界例子比如[2,1,0]并解释循环不变量如何保证结果正确。这样下来即使代码有小错面试官也更愿意引导你而不是直接否定。我在面试别人时最怕遇到那种能默写出题解但讲不清为什么的候选人三指针这道题正是检验“是否真懂”的好题目。如果能顺带说出“这个算法就是三路快排的雏形”那基本就是满分回答。5. 常见错误与排查技巧5.1 死循环和指针越界三指针写法最常见的报错就是超时也就是死循环。原因通常是遇到 2 时交换后 i 没有保持不动。假设你写的是while i p2: if nums[i] 0: ... i 1 elif nums[i] 2: ... p2 - 1 i 1 # 错误这里不应该前进 else: i 1对于[2,0,1]第一次交换后得到[1,0,2]i 会变成 1而 p2 变成 1位置 0 的 1 被直接跳过最终结果错误。更危险的死循环发生在某些复杂分布下两步交换之后 i 和 p2 的关系乱掉导致同一段区域被反复处理。排查死循环最直接的方法是打印每一步的 nums、i、p0、p2肉眼扫一遍就能看出问题。不要在代码里硬加一堆条件先确认算法本身是不是标准写法。另一个相关问题是数组越界。如果你把 p2 初始化为len(nums)访问 nums[p2] 就会越界如果你把循环条件写成i p2但 p2 变成 -1同样会出问题。好在 Python 的负索引不会直接抛异常它会从末尾往前取反而让你更迷惑。所以写代码时对 p2 的维护要格外小心交换后必须立刻更新 p2循环条件也要严格遵守。5.2 交换逻辑写错另一个常见问题是把 0 和 2 的处理条件写反。有人一开始会想“遇到 0 就放左边遇到 2 就放右边”但写if nums[i] 2时交换成 nums[p0]或者写elif nums[i] 0时交换 nums[p2]这就会把数组打乱。为了避免这种低级错误我建议在写代码前先在心里明确三个区间的位置p0 指向 0 区右侧p2 指向 2 区左侧。0 和左边交换2 和右边交换绝对不能交叉。还有人在遇到 2 时加上if p2 i的守卫想避免自我交换。其实不需要自我交换不影响正确性反而让你更容易理解算法。加了额外判断反而增加出错概率。保持最简洁的版本再逐步加注释就好。在 LeetCode 上提交时常见的报错是Wrong Answer而不是Runtime Error因为你可能交换错了但没越界所以调试时优先检查逻辑而不是看异常。5.3 用打印调试法检查不变量算法题调试不方便打断点的时候我一般会在关键分支后面加 print把当前状态打出来。比如print(fi{i}, p0{p0}, p2{p2}, nums{nums})放在 while 循环末尾然后输入一个复杂用例[2,0,2,1,1,0]观察 p0、i、p2 和区间是否符合“左侧 0、中间 1、未知、右侧 2”的不变量。如果发现某个位置出现了不符合区间的值就说明交换或指针移动有问题。这个习惯在本地 IDE 里用特别方便LeetCode 网页版不能直接 print 到提交结果但可以在自己的 Python 环境里模拟。检查不变量还有一个好处它能帮你证明算法的正确性。面试时如果能说出“循环不变量是[0,p0)全是 0[p0,i)全是 1(p2,len-1)全是 2每次循环保持不变”面试官基本就会觉得你稳了。这个证明思路很多题解都不会细讲但对深度理解很重要。你不需要写严格的形式化证明但至少要在心里清楚为什么每次交换后这些区间没有被破坏。5.4 给自己写一个随机验证脚本如果你想把颜色分类这类题练到万无一失我推荐写一个暴力对拍脚本。思路很简单随便生成一个只含 0/1/2 的随机数组用标准库 sorted 的结果当正确答案再用你的三指针函数原地排序比较两者是否一致。循环跑几百组随机数据一旦不相等就打印出原始数组和错误输出。import random def sort_colors(nums): ... for _ in range(1000): n random.randint(1, 100) arr [random.choice([0, 1, 2]) for _ in range(n)] expected sorted(arr) sort_colors(arr) if arr ! expected: print(failed, arr, expected) break else: print(all ok)这个脚本本质上是在做属性测试帮我抓到的 bug 比手算多得多。刷题不只是 LeetCode 上点提交本地建立这种小工具能够有效提高代码的健壮性也顺便训练了工程能力。很多大厂的笔试环境是不允许在线调试的但如果你平时就有这种对拍的思维写出来的代码自然会更可靠。6. 题型变式与扩展思路6.1 K种颜色怎么办颜色分类的扩展问题是如果数组里有 K 种颜色而不是固定的 3 种怎么做如果 K 比较小且已知计数排序依然是最省事的方案因为它只依赖 K 个计数器时间 O(n)空间 O(K)。如果 K 很大但要求原地可以用递归的荷兰国旗思路先按中间值分成两半再对左半和右半继续划分类似于三路快排的递归版本。这种问题在面试中虽然不常考但能展现出你对 partition 思想的理解深度。一句话总结颜色分类考的是三划分K 种颜色就是递归三划分或多路划分。我在面试中也会问过候选人类似的问题如果让你把数组按奇偶分成前后两半你怎么做这和颜色分类的 0/1/2 几乎是一模一样的套路只是少了一个中间区。如果候选人能主动指出“这就是荷兰国旗问题的一个特例”我基本会给出一个不错的评价。所以刷题的时候不能只满足于 AC还要想清楚它和哪些更一般的问题相关联。6.2 相似题与知识点串联热题100里有很多题和颜色分类共享底层思想。最直接的是 LeetCode 283 移动零把 0 移到数组末尾其他元素保持相对顺序。它只需要两个指针本质上是“二分类”的稳定版。还有 LeetCode 905 按奇偶排序数组也只要两个指针。稍微绕一点的是剑指 Offer 21 调整数组顺序使奇数位于偶数前面同样是一道双指针 partition 题。如果你把颜色分类吃透这些题型的核心框架基本都能复用差别只在于“分几类”和“是否要保持稳定”。这里整理一个我自己的相似题对照表方便你们复习题目核心思路与颜色分类的关系283 移动零双指针把非零往前移二分类只有目标元素和其余元素905 按奇偶排序数组双指针交换奇偶二分类但不要求保持相对顺序剑指 Offer 21 奇数在前双指针相向移动二分类和 905 类似75 颜色分类三指针维护三区间本题本体快排三路 partition递归三划分荷兰国旗思想在排序中的应用最近热题里还有一堆题目像是 994 腐烂的橘子、爱吃香蕉的狒狒表面上看和颜色分类没关系。腐烂的橘子是 BFS 在网格上的逐层扩展爱吃香蕉的狒狒是典型的二分答案题。但刷到后面你会发现算法题最重要的不是背题型而是搞清楚每个算法到底在维护什么状态。颜色分类维护的是数组区间BFS 维护的是队列层级二分答案维护的是搜索区间。能把这些“维护状态”的方法内化热题100才算是真正刷通了。6.3 从颜色分类到热题100后续题的学习方法你现在刷到热题100的第93题后面还有 7 题收尾以及二刷、三刷的计划。我的个人习惯是每刷完一类题就整理一个“一页纸笔记”题目名、核心思路、复杂度、易错点、相似题。颜色分类的笔记我会写成核心思路三指针维护三块区间一趟扫描完成分区。复杂度时间 O(n)空间 O(1)。易错点遇到 2 时 i 不前进循环条件是 i p2。相似题移动零、按奇偶排序数组、快速排序三路 partition。这种笔记不需要很长但要能让你三个月后扫一眼就想起全部细节。热题100刷完不是终点能把每道题的模型抽出来才是真正的收获。颜色分类这个模型很值得单独记一笔因为它的三指针写法在面试中复现率太高了。我见过有的候选人把这道题刷了五六遍但每次都是重新背一遍没有真正总结成自己的套路结果面试官稍微一变型就慌了。反过来如果你能在睡觉前闭着眼睛把这四行核心逻辑默写出来说明它是你的东西了。最后再分享一点个人经验。颜色分类这种题最大的坑不是你不知道三指针而是你“知道但写不对”。我从第一次接触荷兰国旗问题到现在已经刷过很多遍每次重新写还是会习惯性地在纸上画一遍区间图。画图不是浪费时间它是在训练你大脑里的“循环不变量”。当你碰到面试现场紧张的时候只有真正理解的东西才会条件反射般地写出来。建议你把本文的代码自己动手敲一遍再跑几个用例然后关掉题解手写。如果能做到三两分钟写对说明这题已经真正成为你的东西了。后面再遇到移动零、按奇偶排序、三路快排这些变体你会发现它们全是同一个套路。希望这篇刷题笔记能帮你省下一些摸索时间。
