企业官网建设流程全解析

1. 不是排序题，是分区题：先理解题目的真实意图

先说一个有意思的现象：这道题在力扣hot100里属于那种"看起来三分钟就能写完"的简单题，我见过不少人第一次接触它时直接写了个nums.sort()交上去，也通过了。但如果你只是这么过了，其实错过了这道题最核心的训练价值。

题目本身不复杂：给定一个长度为 n 的数组，里面只出现 0、1、2 三个数字，分别代表红色、白色、蓝色，要求原地排序，让所有 0 在前、所有 1 居中、所有 2 在后，并且不能使用标准库的排序函数。进阶要求是"仅使用常数空间的一趟扫描"。

第一次看到"一趟扫描"这个条件，很多人觉得莫名其妙：我都排序了，怎么可能只扫描一趟？其实题目真正想考察的不是"排序能力"，而是"分区能力"。你可以把数组看成一块被涂了三种颜色的画布，任务不是从零开始重新组织数据，而是用最少的移动次数，把三种颜色分成三个连续的块。这就是经典的"荷兰国旗问题"——因为荷兰国旗恰好是红白蓝三色条纹，算法的目标就是让数组呈现出国旗那种三段式分布。

为什么force上把这道题放在hot100里？因为它背后是三路划分算法，也就是三向切分快速排序的雏形。你把这个点吃透了，后面理解某些经典排序优化、双指针类题目，都会顺畅很多。

1.1 题目约束的潜台词

先看两个容易被忽略的约束：原地和一趟扫描。

"原地"意味着不能开一个新的等长数组再拷贝回去，空间复杂度必须压到 O(1) 级别。"一趟扫描"意味着每个元素最多被访问常数次，不能先遍历一遍统计数量、再遍历一遍回填。这两个约束组合在一起，基本就是在暗示你：这道题需要用指针在遍历过程中直接把元素放到它该去的位置。

如果不考虑这两个约束，解法其实非常多。比如最无脑的计数排序：遍历一遍数出 0、1、2 各有多少个，再按顺序回填。这个方法时间复杂度也是 O(n)，空间 O(1)，但它需要扫描两遍，不满足进阶要求。再比如自己实现一个快速排序，时间复杂度 O(n log n)，虽然能过但完全浪费了"只有三种值"这个关键信息。

所以拿到这道题，第一反应不应该是"怎么排序"，而是"怎么分区"。排序是通用的，分区是特化的。能用特化方法解决问题时，通用方法往往不是最优解，这个判断力在工程里比会写某个 API 重要得多。

1.2 红色白色蓝色只是个幌子

题目把 0、1、2 包装成红色、白色、蓝色，本质上是在说：数组里的值有一个天然的偏序关系，你需要让这个偏序关系在数组里物理可见。也就是说，这个数组最终从前往后看，一定是 000...111...222... 的形态。

这样的"伪排序"问题其实在很多场景都很常见：某个字段取值只有有限的几种，比如状态码、类别标签、优先级级别，你不想调用重量级的排序算法，只想线性扫一遍把它们归类放好。颜色分类只是把这个问题用一种极具记忆点的形式包装了出来。

理解这一点之后，你再去看那些"只包含 0 和 1""只包含 0、1、2"的题目，思维方式就会彻底改变——你不是在排序，你是在做一次原地分区。

2. 计数排序能过题，但过不了进阶要求

我先把最没有技术含量的解法放在这里，因为它在面试里也不是完全没用：作为一个基线方案，它的正确性最容易被验证，而且可以作为引导出更优解法的起点。

def sortColors(nums): cnt = [0] * 3 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)，额外空间只有长度为 3 的计数数组，可以视为 O(1)。

大多数情况下，这道题用这个版本就能直接通过判题。但面试官如果追问"你能做到一趟扫描吗"，你就要做好继续优化的准备。为什么计数排序不是理想答案？因为遍历了两遍数组。在某些场景下，数据不是存在内存里的数组，而是一个只能读取一次的流，比如实时日志分类、传感器数据过滤。这时候两遍遍历的方案直接不可用。题目里特别强调"一趟扫描"，其实是在模拟这一类真实场景：数据只能过一遍，你必须在这过一遍的过程中把分类做完。

还有一个容易踩的坑：有人觉得计数排序是稳定的，而三指针交换会破坏稳定性。这个说法本身没错，但在这道题里稳定性没有意义——0、1、2 内部的相对顺序根本无所谓。即使把两个位置不同的 2 互相换了位置，最终数组依然满足要求。你只要记住：这道题只关心值所属的类别，不关心同类之间的相对顺序。

3. 三指针的推导过程：从快排分区到三路划分

如果你写过快速排序的 partition 函数，对"双指针分区"应该不陌生：选一个基准值 pivot，用一个指针从头往后扫，另一个指针从尾部往前扫，把小于等于 pivot 的元素放左边，大于等于 pivot 的放右边，最终数组被切成两段。

颜色分类本质上是把"两段"扩展成"三段"。快速排序的双指针分区只能区分"小于等于"和"大于"，但这里需要区分"等于 0""等于 1""等于 2"三类。你当然可以连续做两次两路划分，但那就变成两趟扫描了。所以需要三个指针，在一次遍历中同时维护三个区域。

怎么设计这三个指针？我建议不要死记硬背代码，而是先定义好循环不变量，再让代码去维持这个不变量。所谓循环不变量，就是循环过程中始终保持不变的性质。这里我们维护的是：

• 区间[0, p0)内的所有元素，一定都是 0；
• 区间[p0, i)内的所有元素，一定都是 1；
• 区间(p2, n-1]内的所有元素，一定都是 2；
• 区间[i, p2]是尚未处理的区域。

注意边界：左闭右开还是左闭右闭，一定要定清楚。这里我采用[0, p0)是 0 区，[p0, i)是 1 区，(p2, n-1]是 2 区，[i, p2]是未处理区。初始化时，p0 = 0，i = 0，p2 = n - 1，此时 0 区和 1 区都为空，2 区也为空，未处理区是整个数组，不变量成立。

然后从i开始扫描，每次看nums[i]的值：

• 如果是 0，说明它应该去 0 区。把nums[i]和nums[p0]交换，交换后 0 区向右扩展一位，p0 += 1。同时因为交换过来的nums[i]原本是nums[p0]，而不变量保证nums[p0]是 1（或者当p0 == i时就是我们自己），所以交换完成后当前位置的值已经满足 1 区的要求，i可以继续前进。
• 如果是 1，它本来就该待在 1 区，直接让i += 1，把当前位置纳入 1 区。
• 如果是 2，它应该去 2 区。把nums[i]和nums[p2]交换，2 区向左扩展一位，p2 -= 1。但这里有一个关键区别：交换过来的值是未处理区最右边的值，它可能是 0、1、2 中的任何一个，完全没有被检查过，所以i不能前进，要留在原地继续判断。

3.1 为什么 0 分支可以直接前进，2 分支不行

很多初学者卡在这一点上：同样是交换，为什么nums[i] == 0时i要自增，nums[i] == 2时i不自增？

我这么说你就明白了。当nums[i] == 0时，我们把i位置的 0 和p0位置的元素交换。p0指着什么位置？指针p0的定义是 0 区的最右边界，也就是说p0一定小于等于i（因为 1 区在 0 区右边）。如果p0严格小于i，那么nums[p0]是已经处理过的、不变量保证为 1 的元素；如果p0 == i，那就是自己和自己交换，交换后还是 0。所以无论哪种情况，交换后i位置的值都不可能是 2，再给i自增就是安全的。

而当nums[i] == 2时，我们是从p2位置把它换过来。p2指向的是未处理区的最右边，nums[p2]是从来没有被检查过的值，换成 0 或 1 都还好，万一下一次又是 2，你直接i自增就会漏掉一个 2。所以必须让i停在原地，重新检查交换过来的值。

这个细节是整个算法设计里最精妙也最容易被写错的地方。理解了它，代码才不会写成一团浆糊。

3.2 手动走一遍完整流程

我拿一个典型用例手推一遍：nums = [2, 0, 2, 1, 1, 0]，初始p0 = 0, i = 0, p2 = 5。

第一步：nums[0] = 2，和nums[5] = 0交换，数组变成[0, 0, 2, 1, 1, 2]，p2 = 4，i仍为 0。

第二步：nums[0] = 0，和nums[0]自己交换，p0 = 1，i = 1，数组不变。

第三步：nums[1] = 0，和nums[1]自己交换，p0 = 2，i = 2，数组不变。

第四步：nums[2] = 2，和nums[4] = 1交换，数组变成[0, 0, 1, 1, 2, 2]，p2 = 3，i仍为 2。

第五步：nums[2] = 1，i = 3。

第六步：此时i = 3, p2 = 3，循环条件i <= p2仍然成立。检查nums[3] = 1，i = 4。循环结束。

最终结果[0, 0, 1, 1, 2, 2]完全正确。你可以看到，即使i和p2最终指向同一个位置，如果循环条件用的是i < p2，第六步就不会执行，nums[3]这个 1 就没有被确认。这一点在后面讲边界时会再单独说。

4. 参考实现与边界条件：while 循环为什么是标准答案

先给出可以直接抄的代码，再逐个解释边界条件。我平时习惯用 Python 写题，所以先用 Python 演示：

def sortColors(nums): n = len(nums) p0, p2, i = 0, n - 1, 0 while i <= p2: if nums[i] == 0: nums[p0], nums[i] = nums[i], nums[p0] p0 += 1 i += 1 elif nums[i] == 1: i += 1 else: nums[p2], nums[i] = nums[i], nums[p2] p2 -= 1

C++ 版本几乎一模一样：

class Solution { public: void sortColors(vector<int>& nums) { int n = nums.size(); int p0 = 0, p2 = n - 1, i = 0; while (i <= p2) { if (nums[i] == 0) { swap(nums[p0], nums[i]); ++p0; ++i; } else if (nums[i] == 1) { ++i; } else { swap(nums[p2], nums[i]); --p2; } } } };

Java 也是同样的结构：

class Solution { public void sortColors(int[] nums) { int p0 = 0, p2 = nums.length - 1, i = 0; while (i <= p2) { if (nums[i] == 0) { int tmp = nums[p0]; nums[p0] = nums[i]; nums[i] = tmp; p0++; i++; } else if (nums[i] == 1) { i++; } else { int tmp = nums[p2]; nums[p2] = nums[i]; nums[i] = tmp; p2--; } } } }

为什么标准答案几乎都是 while 而不是 for 循环？因为 for 循环在这个场景下反而不直观。nums[i] == 2时i不能前进，如果硬要用 for 循环，你就得在分支里手动处理i的增减，很容易写出"循环变量在函数体内被修改"这种让维护者头皮发麻的代码。while 循环把i的推进规则完全显式化，每一步都看得清清楚楚。

4.1 两个必须记牢的边界

第一个边界是循环条件：i <= p2，而不是i < p2。前面模拟的例子已经演示了如果漏掉i == p2那个位置的判断，最后一个未处理元素就会被跳过。从不变量的角度解释：[i, p2]是未处理区，当i == p2时，这个区间只有一个元素，它确实还没被处理。只有把它处理完，未处理区才真正为空。所以循环必须在i越过p2之后才结束。

第二个边界是交换后指针的更新顺序。先交换再更新指针，这个顺序不能乱。如果把p0 += 1放到交换之前，那交换时p0指向的位置就不是 0 区的下一个放置点，而是 0 区里的最后一个位置，会把 0 放到错误的地方。这种错误在单步调试时非常隐蔽，因为数组往往只是部分错乱，不容易一眼看出来。

4.2 一些特殊输入case

如果nums长度为 0 或 1，进入循环后最多处理一次甚至直接不处理，代码天然正确。如果整个数组全是 0，流程会变成：每次nums[i] == 0，与nums[p0]交换，而p0 == i，等于自我交换，p0和i一起前进直到数组尽头。全是 2 的情况更有意思：每次都与nums[p2]交换，p2一直递减，i一直不动，循环体内的交换每次把末尾的 2 换到前面，又把前面的 2 换到末尾，直到p2减到i之前，循环结束——整个过程依然在 O(n) 内完成，每个位置只被访问常数次。

5. 提交记录里最常见的三种翻车方式

这道题我前前后后在不同时间点写过好几遍，也看过不少人的提交记录，翻车的姿势基本集中在下面这三种。

5.1 2 分支里手贱加了一行i += 1

这是最经典的错误。忘了从p2交换过来的值可能是 2，在nums[i] == 2的分支里顺手i += 1，就会导致从右边换过来的 2 没有经过检查就被跳过了。假如数组是[2, 1, 0, 2]，第一步i = 0时把nums[0] = 2和nums[3] = 2交换，交换完i直接加一变成 1，nums[1] = 1继续处理，最终你会丢掉一个 2 吗？不会丢，因为数组里那个 2 已经被放到末尾了，最终结果依然可能是对的。但换个例子就不一定了。

比如[2, 0, 1]：i = 0时把 2 放到末尾，交换后数组变成[1, 0, 2]，如果i自增到 1，继续处理会发现nums[1] = 0，交换到前面，最终[0, 1, 2]居然也是对的。那这个错误什么时候会真正触发？当你从右边换过来一个 0，而这个 0 原本应该在更靠前的位置，但因为i已经跳过了它，它就可能卡在 1 区里。比如[1, 0, 2]：i = 0时nums[0] = 1，i前进到 1；nums[1] = 0，交换到p0位置，数组变成[0, 1, 2]，还是对的。似乎这个错误在某些小规模用例下总是能巧合地正确？真正的问题出在连续多个 2 的场景，例如[2, 2, 0, 1]：i = 0，交换nums[0]和nums[3]得到[1, 2, 0, 2]，p2 = 2，如果这时i += 1变成 1，nums[1] = 2，再交换nums[1]和nums[2]得到[1, 0, 2, 2]，p2 = 1，i变成 2，循环条件2 <= 1不成立，最终输出[1, 0, 2, 2]——错得离谱。所以只要遇到类似用例，立刻现形。

5.2 交换时用的是nums[p0]和nums[p2]之外的下标

理论上三指针只需要三个下标，但有人会在写nums[i] == 2分支时，把i和p2交换之后，顺手把p2加一而不是减一。这个不算常见，但一旦写错，整个未处理区的大小就完全乱套。更隐蔽的错误是：在处理 2 时，p2已经递减到i左边，却还在继续从nums[p2]处取元素交换，这时p2指向的是已经排好的 0 区或 1 区，把 2 换进去就会把已排序区域破坏。不过这种情况只要循环条件i <= p2写对了，本来就不会进入循环体。

5.3 处理 0 时忘记i += 1

这个错误和 5.1 正好相反。有人记得 2 分支不能给i自增，但到了 0 分支又忘了给i自增，结果 0 分支里交换过来的是 1（或者自己），如果i不自增，下一次循环就会再次检查同一个位置。假设当前nums[i] = 0，nums[p0] = 1，交换后nums[i] = 1，如果i不自增，下一步还是会看到这个 1，然后进入elif nums[i] == 1，i才终于前进。虽然结果可能没错，但这意味着每个原来的 1 都被多算了一次，代码处于"碰巧能用"的状态。一旦遇到p0 == i的自交换情况，这个错误会直接导致i永远卡在原地，进入死循环。所以 0 分支里i += 1不只是效率问题，更是正确性问题。

6. 向后看：三路划分能串起哪些经典题目

刷题最怕孤立的记忆。一道题的价值不在于它本身，而在于它和其他知识点的连接。颜色分类这道题，串起来的知识比你想象的多得多。

6.1 三向切分快排的源头

经典快速排序在处理大量重复元素时性能会退化，因为标准 partition 会把所有和 pivot 相等的元素随机分到两边，导致递归深度接近 n。三向切分快排的核心思路：把数组切分成< pivot、== pivot、> pivot三块，递归时只处理严格小于和严格大于的两块。颜色分类相当于这个思路中 pivot 固定为 1、且只有三类的特例版本。如果你之前不理解三向切分快排的代码为什么长那样，先把颜色分类吃透，再回头看快排优化，会有豁然开朗的感觉。

6.2 迁移到移动零、奇偶分类这类题目

力扣的移动零问题可以看成颜色分类的退化版：只有 0 和非零两类，用双指针就够了。具体做法是维护一个j指向下一个非零元素应该放置的位置，一次遍历把所有非零元素往前挪，最后补零。如果你用颜色分类的三指针思路去想移动零，会发现它其实就是只有 0 分支和 1 分支的简化版，只不过 1 分支变成了"保留当前元素"。

同理，"按奇偶排序数组""把负数放左边、正数放右边"这类题目，本质上都是两路分区，直接套 fast-slow 双指针就能解决。而"把 0 排到最后、保持非零元素的相对顺序"这类带稳定性要求的题目，就不能用原地交换了，需要结合额外空间或者从后往前填充。分清哪些场景可以交换、哪些场景必须保持稳定，是双指针题里很重要的判断力。

6.3 如果颜色变成 k 种，该怎么办

这是面试官非常喜欢的一个追问。如果数组里有 k 种颜色，三指针就不好使了。此时有两个方向：一是用计数排序，扫描一遍统计频次再回填，时间复杂度 O(n + k)，空间 O(k)；二是做多轮分区，每一轮把当前最小或最大的值归位，时间复杂度 O(kn)。实际情况下 k 很小（比如这里 k = 3），计数排序是最优选择；k 很大但值域有限，可以考虑使用桶排序；如果 k 大到接近 n，那说明几乎没有重复，直接调普通快排反而更合理。

所以你看，颜色分类并不只是一道"会写三指针"的题。它教你的是一种方法论的取舍：数据分布的特殊性决定了算法设计的上限。只有三种取值时，一趟扫描是可能的；取值种类很多时，分区法会退化，计数法更有优势。这个思考方式，比记住一个题解重要得多。

如果你正在准备面试，我的建议是：不要满足于代码通过，把这道题的三种解法（计数排序、两趟交换、三指针一趟扫描）都写一遍，然后合上代码本，按三个指针在不变量约束下的推进逻辑，把这个推导过程完整讲出来。能讲清楚的人，双指针的底子才算是真正打扎实了。