企业官网建设流程全解析

1. 项目概述：先搞懂“颜色分类”这道题想考什么

LeetCode 热题 100 的第 75 题“颜色分类”（Sort Colors），大概是所有求职者避不开的一道经典题。题目本身不长：给你一个只包含0、1、2的整数数组，分别代表红色、白色、蓝色，要求把它们原地排序成0、1、2的顺序排列。

题目光看表面会觉得很简单——“不就排个序吗，sort 一下不就完了”。但这道题真正要考察的，恰恰不是你会不会调sort，而是三件事：数组遍历的指针设计、原地交换的边界控制、以及你能否识别出它其实是经典“荷兰国旗问题”。面试官想看到的是你能不能在线性时间和常数空间内解决它，而不是依赖 STL 或者额外开一个数组。

我在实际刷题和整理面试题的过程中，见过太多人栽在这道题上：有人上来直接nums.sort()，被追问一句“如果你不能用内置排序怎么办”就卡住；也有人知道要双指针，但交换逻辑写得漏洞百出，最后在某些测试用例上翻车。这其实反映出一个普遍问题：光知道“双指针”四个字不够，你必须真正理解每个指针的含义和每一步交换的后果。

这篇文章会把75. 颜色分类从题目本质、推导思路、三种解法的完整代码、边界调试到变体延伸一次讲透，让不管是第一次刷题的新手还是准备面试冲刺的老手，都能从这里拿走一份可以直接复用的解题模板。废话不多说，先从题目本身拆起。

1.1 核心需求解析：题目还原与条件限制

原题描述大致是这样：一个长度为n的数组nums，里面只有0、1、2三种元素，要求原地排序，使得数组变成“所有 0 在最前面，所有 1 在中间，所有 2 在最后面”。注意几个关键约束：

• 你只能原地修改数组，不能额外开一个数组来计数字符然后回填。
• 高级要求是：一趟扫描（one-pass）完成，时间复杂度O(n)，空间复杂度O(1)。
• 元素只有三类，这在很多排序问题里属于特殊结构，不能用常规排序的思维去套。

举个最简单的例子：nums = [2,0,2,1,1,0]，排序后应该变成[0,0,1,1,2,2]。

这里有一个初学者最容易忽略的点：题目要求的是“原地”，所以一切引入新数组的做法，即使思路正确，也天然失分。面试里一旦你说“我准备先统计 0、1、2 的个数，再重新填回原数组”“数组是会变的，你统计完数字之后确实可以填，但这就是破坏原题的意图——第一它不是原地，第二这也埋下了“如果是其他类型数据就没法排序”的隐患。”

1.2 为什么说它是荷兰国旗问题的变体

荷兰国旗问题（Dutch National Flag Problem）由计算机科学家 Dijkstra 提出：问题的背景是有红、白、蓝三色旗子乱序排列，要求把它们按颜色排成红、白、蓝的顺序，并且只能用一次遍历和常数空间。这正是75. 颜色分类的原型。

为什么这个模型特别经典？因为它代表了“三态分区”这一类问题。常见的快速排序里的三路划分（3-way partition），处理排序数组里大量重复元素时，就是把数组分成< pivot、== pivot、> pivot三个区域。颜色分类本质上就是在做一个特殊的三路划分：pivot = 1，所有小于 1 的放左边，大于 1 的放右边，等于 1 的放中间。所以你一旦掌握了荷兰国旗的模板，后面遇到快排优化题、三指针分区题，都能直接迁移。

2. 思路演进：从无知到最优解的三层递进

刷题最重要的不是背答案，而是建立一条从暴力到最优的推导链。你自己能推理出来，面试时才能应对追问。这里我按我的理解把思路分成三个层次。

2.1 第一层：敢想“暴力法”——桶计数回填

最直观的思路是：既然元素只有0, 1, 2三类，那我数一下每个类有多少个，然后按顺序填回去。

def sortColors(nums): counts = [0, 0, 0] for x in nums: counts[x] += 1 idx = 0 for val in range(3): for _ in range(counts[val]): nums[idx] = val idx += 1

这个解法的时间复杂度是O(n)，空间复杂度O(1)（如果硬说 counts 是常数大小的数组）。但它要遍历两遍数组：第一遍计数，第二遍回填。在面试里，如果你先给出这个解法作为“baseline”，有经验的面试官会接着问：你能不能一遍扫描就完成？这就自然过渡到双指针解法。

而且，从工程角度批评这个方案的话：它完全依赖元素的“值”恰好是0,1,2这个连续整数，一旦换成其他枚举类型，就不具备通用性。但作为解题的第一版，它至少能帮你快速验证自己是否理解题意。

我在面试过别人的过程中，经常发现一个现象：很多人连这个“笨办法”都写不顺，比如统计之后忘了把idx归零，或者第二层循环忘了把val和index区分开。所以我会建议：哪怕是暴力解法，也要当成真正要提交的代码来写，变量命名要清晰。

2.2 第二层：双指针计数思想的雏形——两遍扫描优化版

那能不能不统计、直接用交换？可以。先想一个弱化版的问题：如果只需把 0 放到最前面，2 放到最后面，1 留在中间，那么可以用左右两个指针：

• 左指针left指向当前已排好 0 的边界，初始为 0。
• 右指针right指向当前已排好 2 的边界，初始为n-1。
• 用一个遍历指针i扫描数组。

从左到右扫描的时候，如果nums[i] == 0，就和nums[left]交换，left++，i++；如果nums[i] == 2，就和nums[right]交换，right--，但注意此时i不能急着加一，因为换回来的新值还没检查；如果nums[i] == 1，直接i++。

这里加了个“如果”——你看，这其实就是完整的荷兰国旗解法。所以第二层思路并不需要单独写代码，它其实是通往第三层的桥梁。关键在于理解“为什么nums[i] == 2交换后不能加一”，这是几乎所有 bug 的源头。

2.3 第三层：最优解——一遍扫描三指针交换（荷兰国旗三色旗结构）

最终版解法里其实有四个变量：left、right、i，外加一个数组本身。它们各有清晰的职责：

• left指向“下一个 0 应该放的位置”，它左边（不含 left）的区域全部是 0。
• right指向“下一个 2 应该放的位置”，它右边（不含 right）的区域全部是 2。
• i是当前遍历指针，它负责一路扫过那些“待处理”的元素。
• 数组的中间区域[left, i)全部是 1，(right, n-1]全部是 2，[i, right]是未处理的乱序区域。

这个结构非常像一条流水线：左边是已经处理完的 0 区，中间是 1 区，再往右是未知区，最右边是 2 区。每一步都在把未知区变短，直到i > right时所有未知区域清空，排序自然完成。

很多资料里把这个算法总结为一句口诀：“遇 0 换左，遇 2 换右，遇 1 不动。”但我个人不太建议只背口诀不画图，因为一旦你离开纸笔、面对手撕代码环节，很容易搞混 left 和 i 要不要同时前进。后面我会专门画一张执行轨迹表，把每一步的数据变化梳理一遍。

3. 核心实现：三种解法的完整代码与执行轨迹

我这里会给出三种语言的实现示例，重点放在 Python 和 Java 上，因为面试中这两门语言出现频率最高。代码都基于 LeetCode 官方判题的标准函数签名来写。

3.1 基础版：用 Python 实现计数回填

先从这个最容易理解的版本开始。它虽不是最优，但适合用来验证思路、跑通测试。

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

注意一个细节：计数回填法虽然简单，但它的前提是数组只会出现0,1,2，一旦题目改成“包含其他任意值”，这个方案就直接报废。所以它只能作为热身，不能作为最终提交到面试的答案。但也不要小看它：如果你在压力面时脑袋一片空白，写一个能过的版本保底，总比卡在那里不出代码要好。

3.2 进阶版：Java 实现一遍扫描三指针

现在写核心的三指针解法。我要先给你一个完整的 Java 版本，再逐行拆解。

public void sortColors(int[] nums) { int left = 0, right = nums.length - 1; int i = 0; while (i <= right) { if (nums[i] == 0) { swap(nums, left, i); left++; i++; } else if (nums[i] == 2) { swap(nums, right, i); right--; } else { i++; } } } private void swap(int[] nums, int a, int b) { int tmp = nums[a]; nums[a] = nums[b]; nums[b] = tmp; }

这段代码看起来只有十几行，但其实每个分支都有讲究。我把容易错的地方提前挑出来说：

• while (i <= right)的边界条件是<=而不是<。为什么？因为当i == right时，最后一个位置还没有被处理，必须循环到i == right + 1才能结束；如果用<，最后一个元素永远不会进循环。
• nums[i] == 0分支里交换后i++：因为left左边都是 0，left指向的位置要么是i本身（前面全是 1），要么是已经遍历过的位置，所以换过来的值不可能再是 2，可以放心前进。
• nums[i] == 2分支里交换后不i++：因为从right换过来的值是未知的，可能是 0，可能是 1，还可能是 2，必须留在原地再检查一次。
• nums[i] == 1直接i++：1 本来就应该留在中间，不需要交换。

这个解法的时间复杂度是严格O(n)，因为每个元素最多被访问常数次；空间复杂度O(1)，仅用了几个指针变量。正是题目要求的“一趟扫描 + 常数空间”。

3.3 最佳实践：遍历过程静态推演

我觉得光给代码不够，必须推演一遍，才能真正理解指针为什么这样移动。拿nums = [2,0,2,1,1,0]举例，初始状态：left=0, i=0, right=5。

我特意没有简化表格，因为亲手一步步推演，比看十行解释更有效。你注意第 4 步：交换后i仍然是 2，而此时nums[2]变成了 2，被交换出来的 2 移动到了right=3指向的位置，正确。如果你在交换 2 之后错误地执行了i++，就会跳过这个未知元素，后面还要再处理，甚至可能引发越界。

3.4 另一种优雅写法：Python 一行版与划分为 “0 区 1 区 2 区”

用 Python 写同样逻辑时，很多老手会稍微压缩一下代码，但我建议面试时还是写得展开一点，方便解释。这里给一个简洁但可读的版本：

def sortColors(nums): left, right = 0, len(nums) - 1 i = 0 while i <= right: if nums[i] == 0: nums[left], nums[i] = nums[i], nums[left] left += 1 i += 1 elif nums[i] == 2: nums[right], nums[i] = nums[i], nums[right] right -= 1 else: i += 1

有人调侃这道题的 Python 最短答案可以写成nums.sort()，但面试官大概率不会满意。如果你想玩，可以试试在一行里用推导式，但那种写法只适合刷题自娱，不适合面试展示——因为面试官想看的是你对指针逻辑的掌控，而不是 Pythonic 魔法。

4. 避坑指南：最常见的 bug 与调试实录

这段是我最想写的部分。我在无数次的手撕代码环节里，看到过各种千奇百怪的错误版本，也曾经自己在买菜时对着数组走神推演。以下问题几乎每个刷这道题的人迟早都会碰到。

4.1 指针边界：为什么循环写i <= right而不是i < right

这是最经典的边界问题。假设数组是[1,1,2]，left=0, right=2, i=0：

• nums[0]=1，i++变成 1。
• nums[1]=1，i++变成 2。
• 此时i=2，若循环条件是i < right（2 < 2为假），循环直接退出，nums[2]永远没被处理，数组是错的。
• 而i <= right时，还会进入循环，发现nums[2]=2，与right交换，right--变成 1，此时i=2 > right=1，退出，正确。

所以记住：i必须能访问到right指向的那个位置，否则最后一个元素会被遗漏。

4.2 交换 0 和交换 2 的不对称性

我见过一个高频率 bug：有人写两个分支都交换后i++，结果排序结果不稳定地错。下面这个版本就是典型错误：

# 错误示例：交换 2 后 i++ 导致跳过检查 while i <= right: if nums[i] == 0: nums[left], nums[i] = nums[i], nums[left] left += 1 i += 1 elif nums[i] == 2: nums[right], nums[i] = nums[i], nums[right] right -= 1 i += 1 # 这里错了 else: i += 1

用nums = [2,1,0]测试：i=0，交换 2 后数组变[0,1,2]，right变 1，i错误地变成 1，跳过检查nums[0]=0，最后数组是[0,1,2]表面看着正确？换nums = [2,0,1]再试：i=0，交换 2 后数组变[1,0,2]，right=1，i变成 1，此时检查[1,0,2]中nums[1]=0，交换到 left 变[0,1,2]，似乎也碰巧对了。那如果换nums=[2,2,1,0]呢？用错误版本跑：

• i=0，交换 2 到末尾，数组[0,2,1,2]，right=2，i 变 1。
• i=1，数组[0,2,1,2]，nums[1]=2，交换到 right，数组[0,1,2,2]，right=1，i 变 2。
• 此时i=2 > right=1，循环退出，输出[0,1,2,2]，看似正确。

但换个用例[0,2,1,2]（注意这里开头的 0 被错误地换到 left，然后 i++）：

• 初始 i=0，nums[0]=0，交换后不变，left=1, i=1。
• i=1，nums[1]=2，交换到 right，数组[0,1,2,2]，right=2，i 变成 2。
• 循环继续（2<=2），nums[2]=2，交换到 right，数组[0,1,2,2]，right=1，i 变成 3。
• 此时 i=3 > right=1，退出，输出[0,1,2,2]，仍然碰巧正确。

这其实是一种“碰巧正确”的诱惑——有些错误版本在某些用例下会给出正确结果，但在另一些用例下会翻车。比如[2,0,1,2]：

• i=0，nums[0]=2，交换到 right，数组[1,0,2,2]，right=2，i 变成 1。
• i=1，nums[1]=0，交换到 left=0，数组[0,1,2,2]，left=1，i=2。
• 此时 i=2==right=2，循环继续，nums[2]=2，交换后 right=1，i=3，退出，正确。

老实说我甚至找不出一个稳定翻车的反例。但你敢在面试中赌这个吗？赌输了就全盘皆输。关键是逻辑上你无法证明交换 2 后i++是安全的，所以工程上必须不带i++。面试官问“为什么”的时候，你要能说出“换回来的值未知，需要留待检查”这句话。

4.3 特殊情况：全零、全二、空数组

• 全 0：[0,0,0]，left 一路推进，i 一路推进，right 不动，结果正确。
• 全 2：[2,2,2]，每次交换 2 到 right，right 递减，i 不变，直到i=0, right=-1，退出，正确。
• 空数组：left=0, right=-1，while (i <= right)即0 <= -1为假，直接退出，正确。
• 单个元素：直接退出或直接走一个分支，只要边界条件写对就没问题。

我强调空数组的原因在于：有些人的循环优化成while (i < nums.length)，遇到[0]时没问题，但遇到[2,1]时可能把 2 换到右边界后又把 1 换走，产生错误。最稳妥的还是标准的荷兰国旗循环。

4.4 一个常见的调试技巧：在所有交换处打日志

如果你实在调不通，最快的办法是在三处分支里各打一行日志，打印i, left, right, nums[i]，然后用 LeetCode 的示例数组走一遍。我当初学这道题时就是这样做的，五分钟内就能定位到指针错位点。等到理解之后，再把日志删掉。别否认调试打印的价值，它在学习阶段比任何脑内推演都直观。

5. 扩展与实战：从颜色分类到更广的算法场景

掌握了解法本身只是第一步。能够在后续题目里复用它，才算真正学透。我记得有次在群里看一个同学做快排三路划分优化题，卡了很久，后来发现他其实完全可以用荷兰国旗的模板。所以这里我想把它的迁移场景列清楚。

5.1 关联题目一：移动零 (Move Zeroes)

力扣 283 题“移动零”：给定一个数组，把非零元素移到前面，保持它们的相对顺序，所有 0 移到末尾。这题其实可以看成一道两色分类：把数组分成“非 0 区”和“0 区”。用类似思想，一个指针j记录非零区末尾，遍历时遇到非零就交换到j，j++。

def moveZeroes(nums): j = 0 for i in range(len(nums)): if nums[i] != 0: nums[i], nums[j] = nums[j], nums[i] j += 1

可以对比颜色分类的三指针：这题退化成两指针（一快一慢），本质是“分区思想”的简化版。如果你能独立把颜色分类迁移到移动零，说明你已经理解了三态分区到二态分区的递进关系。

5.2 关联题目二：快速排序的三路划分

标准快速排序中，处理大量重复元素时，经典的两路划分（小于等于放左、大于放右）会退化到O(n^2)。这时可以采用三路划分：把数组分成< pivot、== pivot、> pivot三部分，然后递归排序小于区和大于区。这几乎就是颜色分类的模板：

• left表示“下一个小于 pivot 的元素放置位置”。
• right表示“下一个大于 pivot 的元素放置位置”。
• i扫描，注意== pivot的不要交换，留在中间。
• 区别只是 pivot 不一定是固定值 1，而是基准值。

所以刷完颜色分类，再去看快排优化、荷兰国旗分区，你会觉得很多代码模板似曾相识。这也是我推荐优先掌握这道题的原因：它是一系列分区算法的最小公共内核。

5.3 关联题目三：K 种颜色的泛化

如果数组里有k种颜色（值域0到k-1），要求排序排列，怎么办？三指针不再适用，因为分区不止三个。常见解法有两个方向：

• 方向一：执行两遍扫描，第一遍把最小的颜色归位，第二遍处理剩余颜色，复杂度 O(kn)。
• 方向二：用计数排序思维，统计每个颜色的数量再回填，复杂度 O(n+k)。

所以这道题的“单次遍历三指针”是特殊的k=3优化版本。面试里如果往这个方向追问，你要能说清楚为什么三指针不能直接推广到任意 k。

5.4 工程启示：什么时候该用“额外空间换时间”

有人说颜色分类用计数排序最简单，为什么非要执着于一遍扫描呢？工程上，如果数组规模不大、性能要求不高，计数排序完全合理。但算法面试考的不是“这个场景下空间够用吗”，而是训练你在资源受限时如何敏锐地找到常数空间的解法。这个思维习惯在实际系统里很有价值：有时你不能开一个辅助数组，不是因为空间不够，而是因为数据量巨大、无法一次性载入内存；有时是内存带宽受限，宁可多走几轮循环，也不愿意引入额外分配。

我在写过一段时间工程代码后，回过头来再看这道题，体会更深了：能写出O(n)时间O(1)空间的版本，代表你在“原地修改”这件事上不会被变量枝枝节节绕晕，这恰恰是处理大型数据流时的重要基本功。

6. 总结与自测：三道自测题帮你判断是否真懂了

我不想用那种“综上所述”的收尾方式，也不想堆术语。最后我想留三个自测题，你可以拿它们检验自己是不是真的吃透了这道题。

1. 手写三指针解法，并解释每个分支中指针的移动规则，特别是交换2后为什么要保持i不动。
2. 口头描述一遍荷兰国旗的分区不变式：循环过程中，nums[0..left-1]==0，nums[left..i-1]==1，nums[right+1..n-1]==2，验证一次[2,0,2,1,1,0]的每一步执行。
3. 尝试不使用三指针，而是写一个两遍扫描的版本，分析它为什么比三指针多一次遍历，在什么场景下这种“多一次遍历”反而更好（比如数据流场景里，你可能还要统计其他信息）。

如果你能流畅完成这三题，那么这道 Hot 100 题目对你来说就已经不是“背代码”，而是真的属于你了。我个人的体会是：算法题最忌讳光看不写、光写不想。每做一道题，都应该问自己三个“为什么”：为什么用这种数据结构，为什么要这样处理边界，为什么复杂度是这个量级。能回答上来，才算真正学会。