企业官网建设流程全解析

先交代一下背景：我每年都会把这题拿出来给准备跳槽的朋友讲一遍，因为力扣 Hot 100 里的“颜色分类”（LeetCode 75. Sort Colors），可以说是双指针专题里性价比最高的一题。题目本身极其简短，就是给一个只有 0、1、2 三种值的数组做原地排序，但背后牵扯出的荷兰国旗问题、循环不变量、三路 partition 这些概念，几乎能把算法面试的基础能力串起来考一遍。

这篇文章适合三类人看：一是正在刷力扣 Hot 100、卡在这道题或者背了答案却不懂原理的人；二是写过三指针版本但总在边界条件上翻车的人；三是想搞清楚“面试官为什么要问这道题、还会怎么追问”的求职者。我会按自己的实战习惯来写：先讲清楚题目在考什么，再给保底解法，然后完整推导一趟扫描的三指针写法，最后把调试现场和面试追问一并交代。

1. 先把题目看透：颜色分类到底在考什么

1.1 题目原文与第一反应

题目原文不长：给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们用整数 0、1、2 分别表示红色、白色和蓝色。约束条件是：不能使用库里的 sort 函数，进阶要求是设计一个仅使用常数空间的一趟扫描算法。

我第一次做这题时，第一反应和大多数人一样：“这有什么难的，直接 sort 不就完了？”但题目偏偏把“不使用库的 sort 函数”写在最前面，这就是在告诉你：考点根本不是排序本身，而是你能否利用数据分布的特殊结构，设计出比通用排序更省时间、更省空间的归类方案。

数组里只可能出现三种值，这意味着一切基于比较的通用排序算法都是杀鸡用牛刀。你真正需要抓住的信息是“只有三类元素”，然后利用这个结构把数组原地分成三段。这个认知一旦建立，解法就是水到渠成的事。

1.2 从“荷兰国旗”到“颜色分类”：经典问题的来由

这道题有个更响亮的名字：荷兰国旗问题，由计算机科学家 Edsger Dijkstra 提出。荷兰国旗恰好是红、白、蓝三色横条，把乱序的元素重新归类成三段连续色带的操作，和整理一面打乱的国旗非常像，所以得了这个名字。

理解这个背景不是为了让文章显得有文化，而是为了帮你记忆算法结构。你可以把数组想象成三块连续区域：最左边一段全是 0（红），中间一段全是 1（白），最右边一段全是 2（蓝）。算法做的所有事情，就是维护这三段区域的边界指针，一边扫描一边把遇到的元素丢进它该去的区域。手里拽着这个画面，代码基本不会写错。

1.3 为什么这题能进 Hot 100

Hot 100 是力扣根据面试出现频率和知识点覆盖面筛出来的题单，颜色分类能稳定占一个名额，是因为它一份题量覆盖了三个高频考点：

• 原地修改数组，考察你能不能摆脱“新建一个数组再拷贝回去”的惯性思维；
• 双指针/三指针技巧，这是面试中出现频率极高的一类数组处理手法；
• 循环不变量思维，也就是“每一轮循环结束后，数组的哪些部分已经满足什么性质”的抽象能力。

这三样东西几乎是所有中等偏上算法题的底层能力。把这题吃透，后面再碰“移动零”、“三数之和”、“接雨水”、甚至快排的三路 partition，都会觉得似曾相识。很多资料会把“颜色分类”放在双指针分类下，但其实它更像一根连接排序和指针两座山的绳子。

2. 暴力与计数：从最简单的解法说起

2.1 直接排序：为什么被一口回绝

如果你在面试里直接写Arrays.sort(nums)，基本等于告诉面试官“我没理解题目的约束”。这里要分清：不是 sort 本身有错，而是它绕开了出题人想考察的能力。

通用排序算法（比如快排）的时间复杂度是 O(n log n)。对这道题来说，数据只有 0、1、2 三类，理想的归类时间是 O(n)。面试官期待看到的，是你主动发现“这个数组不需要比较排序”这个洞察。所以遇到这种“明明可以调库”的题，先停下来想想约束条件到底在暗示什么，这是面试里很值钱的一个习惯。

2.2 计数排序：两遍扫描的稳妥方案

最直观且完全正确的解法是计数排序。因为值的范围只有 0、1、2，我们可以先遍历一遍统计每种颜色的出现次数，再按顺序把数组重新填满。

def sortColors(nums): count = [0, 0, 0] # 分别记录 0、1、2 的出现次数 for num in nums: count[num] += 1 idx = 0 for color in range(3): for _ in range(count[color]): nums[idx] = color idx += 1

这段代码逻辑简单到几乎不可能出错：第一遍统计，第二遍回填。时间复杂度 O(n)，空间复杂度因为计数数组大小固定为 3，同样算 O(1)。如果你在面试时一时紧张没想出三指针，先写这个版本是完全可以拿分的，甚至可以主动跟面试官说：“这是两趟扫描的思路，我可以再优化成一趟。”这句话本身就是加分项。

2.3 计数排序的局限与面试官的心思

两遍扫描有什么问题吗？单看复杂度没有任何问题，常数空间、线性时间，已经满足题目的大部分要求。但进阶要求里明确写了“一趟扫描算法”，面试官想要的往往就是这个 one-pass 版本，原因有两个：

第一，一趟扫描强制你使用指针维护区域边界，这才能考察你对数组索引和交换细节的掌控力。写两遍扫描的人，不需要思考“换回来的元素是什么”，自然练不到这块。第二，真实工程里的流式场景可能只允许数据读一遍，或者数组大到希望减少写回次数，一趟扫描确实更贴近实际需求。

我的建议是：两遍扫描当保底方案，三指针当主答案。先写正确拿分，再给优化方案，比一上来就背三指针、结果边界处理得一塌糊涂要稳得多。毕竟面试是按点给分，代码正确永远排在“解法炫酷”前面。

3. 一趟扫描搞定：三指针的完整推导

3.1 三指针的循环不变量

先说结论：维护三个指针left、mid、right，整个循环过程中数组始终保持下面这个状态：

• [0, left)区间内全部是 0（红色）
• [left, mid)区间内全部是 1（白色）
• (right, len-1]区间内全部是 2（蓝色）
• [mid, right]区间内是尚未处理的元素

这种“每轮循环结束后数据满足什么性质”的描述，就是算法里常说的循环不变量。写代码时只要保证每轮操作后不变量仍然成立，循环结束时左边是 0、中间是 1、右边是 2，答案自然就对了。

为什么要用三个指针而不是两个？因为数组要被分成四部分：零区、一区、待处理区、二区，四个分区需要三条分界线。两个指针最多只能切出三段，装不下“已处理的 1”和“待处理的数据”这两个不同的区。想通这一点，你就能理解为什么这道题是“三指针”而不是“双指针”。

3.2 分情况讨论：0 怎么办、1 怎么办、2 怎么办

mid指针负责扫描整个待处理区，每轮只看nums[mid]的取值，分三种情况：

• 等于 0：这个元素应该放到最左边的 0 区。把nums[left]和nums[mid]交换，然后left和mid都向右移动一位。为什么mid可以跟着动？因为交换过来的nums[left]只可能是 0 或 1——如果left == mid，换的是同一个元素，必然是 0；如果left < mid，nums[left]原本属于 1 区，必然是 1。无论哪种情况，换到mid位置的值都是“已归类”的，不会破坏中间一区的性质，所以mid可以放心前进。
• 等于 1：白色本来就该待在中间区域，什么都不交换，直接mid++跳过。
• 等于 2：这个元素应该放到最右边。把nums[mid]和nums[right]交换，然后只移动right--，mid不能动。原因很关键：nums[right]是未被处理过的元素，它可能是 0、1 也可能是 2，换到mid位置后必须再看一遍，所以mid要停在原地，留到下一轮继续检查。

这三句话就是整个算法的核心。面试官最常抓的细节就是第三行：交换 2 之后mid动不动。这块逻辑想明白了，代码就是照抄。

3.3 完整代码与复杂度结论

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

循环结束后，所有 0 都在最前面，所有 2 都在最后面，中间的 1 自然归位。复杂度方面：一趟扫描，每个元素至多被处理两次（被换到mid位置后可能再次被检查），整体 O(n)；只用了三个指针变量，空间 O(1)。这已经顶到这道题的最优复杂度了。用 C++ 或 Java 写也是同一套逻辑，只是数组交换的写法略有差异，思路完全一致。

为了确认正确性，我建议手动走一遍nums = [2, 0, 2, 1, 1, 0]，过程如下表：

这个表建议你亲手画一遍，画完你会彻底理解“为什么第 4 步换回 2 之后不动 mid”。

4. 实操踩坑：边界、死循环与调试实录

4.1 最经典的 bug：交换 2 之后不动 mid

我见过太多第一次写三指针的人，在else分支里下意识写成“交换后 mid++、right--”，然后结果完全不对，甚至直接死循环。问题就出在交换回来的那个元素：nums[right]在交换前是未处理数据，它要是 0 呢？此时把 0 换到了mid位置，mid却直接跳过去了，这个 0 就永远没人再检查，最终数组中必然出现错位。

我自己面国内大厂时就写错过一次，面试官没直接说答案，只问了一句“你确定换回来的元素一定是 2 吗？”我当时愣了一下，手动模拟了一遍才意识到问题。这种错误特别容易在紧张时犯，所以我现在的习惯是：写完后立刻拿[1, 2, 0]这种三个数的小用例在脑子里过一遍，能快速暴露这类边界 bug。

4.2 循环条件用 <= 还是 <

标准写法是while mid <= right，因为mid指向待处理区域的第一个元素，right指向待处理区域的最后一个元素，mid == right时这个位置还没被检查。

如果你写成mid < right，会漏掉mid == right时那一个元素。举个具体例子：nums = [0, 1]，初始left=0, mid=0, right=1，处理完nums[0]=0后left=1, mid=1，此时mid == right，这个位置上的 1 还没被检查，但mid < right会让循环直接退出。这个例子里 1 恰好就在正确位置，看不出问题；换个场景就可能翻车。所以循环条件要写<=，配合交换逻辑天然正确终止，不会因为多检查一个“已归位”的元素而出错。

4.3 内存与稳定性：为什么这道题不在乎“稳定排序”

有同学会问：三指针的交换是跳跃式的，会不会破坏原有顺序？答案是不需要关心，因为这道题根本不要求稳定排序。所有 0 都是等价的，你无法区分、也不需要区分“第一个 0”和“第二个 0”，排序完成后它们看起来一模一样。所以交换可以非常随意。

但如果你将来处理的是“按某个 key 分类，同时还要保持同类元素的原始相对顺序”，那就不能这么随便交换了，得考虑稳定 partition 或者引入临时数组。这个差别我建议你记在笔记里，面试被追问“你这个交换稳定吗”时，能讲清楚“这道题不需要稳定”和“什么场景需要稳定”，是很加分的区分度。

5. 面试追问与延伸：从 3 色到 k 色

5.1 面试官爱问的三个 follow-up

据我观察，面试官在这道题之后基本都会追加问题，出现频率最高的是下面三个：

1. “如果数组里不止 3 种颜色，改成 4 种呢？”三指针的核心假设是中间区域只保留一种值，4 色情况下中间要维护两类值，三个指针不够用，需要调整策略或者换回计数排序。
2. “如果要求尽可能少的交换次数呢？”三指针并不是交换次数最优的方案。更优做法是先按计数的三段边界确定每个元素的目标位置，然后只交换错位的元素。这个变体更适合作为拓展题思考，面试时能说出“三指针不是最少交换方案”就已经超出多数人了。
3. “这个思路和快排有什么关系？”三指针本质上就是三路快排的 partition 过程：把等于 pivot 的元素单独放中间，小于和大于的分别放两边。理解了这一点，“颜色分类”就不再是一个孤立题目，而是快排优化的重要前置知识。

5.2 延伸：四色、k 色怎么处理

如果是固定 4 种颜色，可以把三路分区的思想推广成四路分区，维护四个边界指针，但逻辑复杂度上升得很快，写起来容易出错。更通用、更稳妥的方案是回到计数排序：统计每种颜色出现次数后线性回填，时间复杂度仍是 O(n)，空间复杂度 O(k)。因为颜色种类是有限常数，这块额外空间可以忽略不计。

如果颜色种类 k 和数组长度 n 同阶，问题性质就变了：要么允许 O(k) 的额外空间，要么退化成基于比较的排序。这个“k 是常数还是可变”的判断标准，比死记某种解法更有通用价值。我面试别人时，其实更看重候选人能不能讲出这条判断链路，而不是背出某一种实现。

5.3 我的刷题体会与复盘建议

最后讲点我自己的方法。我做这道题时没有急着写代码，而是先在草稿纸上画出三个区间，把三个指针的初始位置标出来，然后手动模拟一个[2, 0, 2, 1, 1, 0]的完整过程。模拟完一遍再去写代码，基本一遍过。这个习惯我一直保留着，处理任何指针类题目都适用——先让指针在纸上跑起来，代码只是把跑的过程翻译成语法。

复盘时，我会把两条容易错的细节写进错题本：一条是“交换 2 之后为什么不动 mid”，另一条是“循环条件为什么是 <=”。这两条才是面试真正考察的东西，不是你能不能背出三行交换代码，而是你对索引和不变量的掌控力。如果你也在刷力扣 Hot 100，我的建议是把这道题和“移动零”“三数之和”“快排的三路 partition”放在一起对比着看，你会发现它们的本质都是用指针把数组切分成若干区域。刷通这一组题，双指针这个专题基本就拿下了。