企业官网建设流程全解析

看一眼标题，很多人可能会觉得“颜色分类”又是一道基础的排序题，直接调排序函数或者数一数0、1、2的个数就完事了。但真正把这题吃透的人都知道，75题是双指针进阶的一个经典入口——它背后是荷兰国旗问题，是后面理解三路快排、循环不变量、双指针调度逻辑的最佳跳板。这篇文章就把我从“暴力解”到“一次遍历双指针”的完整思路、代码细节、踩坑点以及延伸题都捋一遍，希望能帮你把这题彻底放进自己的知识体系里。

1. 粗看是排序，细看是分区：先吃透题目真正想考什么

1.1 题面拆解与定位

原题给了一个只包含0、1、2的整数数组，0代表红色、1代表白色、2代表蓝色，要求原地排序，让相同颜色的元素相邻，并且按红、白、蓝的顺序排列。看起来是排序，但仔细想想，这题的核心不是“排序算法”，而是“分区”——把一个无序的三色数组，按照固定顺序划分成三个连续区间。

面试和刷题里遇到它，最常见的考核点是三个递进层次：

1. 你能不能在不调用排序库的情况下完成；
2. 能不能做到常数空间，也就是原地操作；
3. 能不能做到只扫描一遍数组，把时间复杂度和空间复杂度同时压到最优。

大部分人的第一反应是先统计0、1、2的个数，然后再按数量覆盖回去。这种做法没问题，但它只能满足前两个层次，应付不了第三个。而这题真正的分水岭，恰恰就是第三点。这也是为什么很多题解里会说“这题用计数排序是最直接的思路，但双指针才是最优解”。

1.2 计数排序：最直觉的解法，但只能算热身

先说说大家都想得到的计数排序，因为它最容易写对，也是后面理解双指针方案的基础参照物。

class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ counts = [0] * 3 for num in nums: counts[num] += 1 i = 0 for color in range(3): for _ in range(counts[color]): nums[i] = color i += 1

这个思路很朴素：第一趟遍历统计每个颜色出现的次数，第二趟遍历按红白蓝顺序依次把对应数量的元素写回原数组。时间O(n)，辅助空间O(1)，因为计数数组长度固定为3。

它的缺点也很明显——数组被完整遍历了两遍。从大O角度看没问题，但面试官往往会追问一句“能不能只用一趟扫描搞定”。如果你没有准备，临时想一次遍历的双指针还是有难度的，因为要同时维护多个边界条件。所以接下来我重点讲讲怎么从“两遍”优化到“一遍”。

2. 从两次遍历到一次遍历：荷兰国旗算法是怎么设计出来的

2.1 荷兰国旗问题的直觉锚点

我第一次看到荷兰国旗这个名字时，第一反应是：这和国旗有什么关系？后来才知道，荷兰国旗恰好是红白蓝三色横条，题目用0、1、2代表这三种颜色，用“国旗”来类比“把三种颜色元素排好”的过程，非常形象。

这种分区问题的关键，不是“比较大小”，而是维护若干个有序区间。你可以这样想象：一根绳子拉直放在地上，我们用三个夹子把它分成四段——最左边夹子左侧全是0，两个夹子之间全是1，最右边夹子右侧全是2，中间未处理区域随着扫描不断收缩，直到消失。

三个指针分别管着这三块区域的边界：

• p0：指向最后一个0的右侧位置，表示0区间的结束边界；
• p2：指向第一个2的左侧位置，表示2区间的起始边界；
• i：当前正在扫描的元素下标，同时它也是1区间的结束边界，或者说未处理区域的起点。

每次扫描，我们根据nums[i]的值做三类处理：

• 当前是0，把nums[i]和nums[p0]交换，p0向右移一位，i也向右移一位；
• 当前是2，把nums[i]和nums[p2]交换，p2向左移一位，此时i不动，因为换回来的元素还没有被检查过；
• 当前是1，什么都不用换，i直接向右移一位。

这里有个非常关键、也最容易写错的地方：为什么遇到2并交换后，i不能加1？因为p2位置上的元素是待处理区域的尾部元素，它可能是0、1、2中的任意一个。你换了以后，拿回来的这个新元素必须留在当前位置重新判断一次，否则就会漏掉一个可能不该停留在这里的元素。而p0位置的交换为什么就不用担心？因为根据循环不变量，p0到i之间全都是1，nums[p0]只可能是1（或者在i == p0时，是当前这个0自己和自己交换，结果不变），所以交换后 i 位置的元素必定是1或0，可以直接推进。

这一个区别，就是整个算法最容易翻车的地方。

2.2 循环不变量与边界条件

写成正式一点的循环不变量，大概是这样的：

• 区间[0, p0)内的元素全是0；
• 区间[p0, i)内的元素全是1；
• 区间(p2, len(nums)-1]内的元素全是2；
• 区间[i, p2]内的元素是尚未处理的未知元素。

循环开始时，p0=0、i=0、p2=n-1，所有区间都为空，不变量自然成立。循环每执行一步，要么区间范围更新，要么把未知区间的元素归入某个已知区间，不变量始终不被破坏。当i > p2时，未知区间为空，此时整个数组已经被0、1、2三段完整覆盖，排序完成。

为什么循环条件是while i <= p2而不是while i < n？因为当i越过p2之后，剩下的元素都已经全部确认过是0或1了，不需要再扫描；如果继续让i遍历到数组末尾，可能会把右侧的2区域误处理掉。这在视觉上很像“两个指针从两端往中间夹”，直到中间的空隙完全闭合。

理解了不变量，写代码时就有了底气——你不知道某个边界该怎么处理时，回到不变量里对照一眼，就不会凭感觉乱写了。

3. 手写一遍荷兰国旗解法：代码里的每个细节都在干什么

3.1 Python 标准实现与逐步推演

直接上代码：

class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ n = len(nums) p0 = 0 p2 = 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: # nums[i] == 1 i += 1

用一个小例子推演一遍：nums = [2, 0, 2, 1, 1, 0]。

初始：p0=0, p2=5, i=0，数组原样。

• i=0，元素是2，和nums[5]交换，数组变成[0, 0, 2, 1, 1, 2]，p2=4，i 仍为0；
• i=0，元素是0，和nums[0]交换（自己换自己），数组不变，p0=1, i=1；
• i=1，元素是0，和nums[1]交换（自己换自己），数组不变，p0=2, i=2；
• i=2，元素是2，和nums[4]交换，数组变成[0, 0, 1, 1, 2, 2]，p2=3，i 仍为2；
• i=2，元素是1，i=3；
• i=3，循环条件i <= p2（3 <= 3）成立，元素是1，i=4；
• 现在i=4 > p2=3，退出循环。

最终数组是[0, 0, 1, 1, 2, 2]，符合要求。

注意最后一次循环：i=3和p2=3指向同一个元素，这个元素是我们把原来i=2位置的2换走之后留下的“未知元素”，也就是原p2位置的值，它恰好是1。把它处理后，未知区间才真正清空。如果循环条件是i < p2，这一步就会被跳过，最后的1就漏掉了。

3.2 最容易写错的几个分支

这里我汇总一下刷这道题时大家最容易写错的细节：

我自己的做题经验是：把i当成“扫描枪”，p0和p2是两堵可以推动的墙。遇到0就把0扔到左墙内侧，左墙右移，扫描枪继续；遇到2就把2扔到右墙内侧，右墙左移，但扫描枪必须原地待命，等看清接手的新元素再走；遇到1不用管，扫描枪直接前进。每次写 if-else 分支时，都想想：墙移动了，扫描枪该不该跟着动？

3.3 复杂度分析

这个算法的时间复杂度是O(n)，因为每个元素最多被访问两次（一次是被 i 扫描到并处理，另一次是作为被交换对象在 p2 处被换到 i 后又处理一次）。但总体来看，每一次交换都会把一个元素放到最终位置，循环次数是线性级别的。空间复杂度O(1)，因为只用了几个指针变量，没有借助任何额外数组。

对比计数排序的两遍遍历，荷兰国旗解法的优势并不仅仅在于“少扫一遍”，而在于它把空间和时间都压缩到了极致，并且不依赖元素的值域。这一点在后面的变体题目里会有更明显的体现。

4. 边界测试与踩坑复盘：用测试用例逼出真问题

4.1 极端输入下的循环不变量验证

写完代码，别急着提交，先在本地过一遍边界用例。我常用的测试数据是这几组：

• 全0：[0, 0, 0, 0]
• 全1：[1, 1, 1]
• 全2：[2, 2, 2, 2]
• 倒序：[2, 2, 1, 1, 0, 0]
• 只有两色：[0, 1, 0, 1]、[2, 1, 2]
• 单个元素：[0]、[1]、[2]
• 空数组：[]

逐个跑一遍，确认所有分支都覆盖到了。比如全0场景，会遇到大量“nums[i] == 0并且i == p0”的情况，即自己和自己交换，此时 p0 和 i 同步推进；全2场景，会遇到 i 一直在原地循环，直到 p2 左移到 i 左边才结束；单元素场景，则要确认i <= p2的边界能正确处理而不是越界。

这些用例的价值在于：它们能帮你区分“代码逻辑正确”和“代码碰巧跑通”的区别。多写几组极端值，往往能暴露出很多隐蔽 bug。

4.2 用随机测试做属性验证

还有一种更省事的验证方式——随机测试。用 Python 的 random 生成大量长度为1到20、元素只含0/1/2的数组，分别用计数排序、单指针两次遍历和荷兰国旗一次遍历跑一遍，再把结果排序后比对，或者直接检查排序后的数组是否满足“所有0在最前，所有2在最后”的条件。

import random def check_sorted(nums): prev = -1 for num in nums: if num < prev: return False prev = num return True for _ in range(5000): length = random.randint(0, 20) nums = [random.randint(0, 2) for _ in range(length)] original = nums[:] sort_colors(nums) # 待测函数 if not check_sorted(nums): print("FAIL:", original, "->", nums) break else: print("ALL PASS")

我实际跑下来，发现最容易触发 bug 的是长度在3到7之间、包含大量重复2的数组。比如[2, 0, 2]，如果处理2时 i 错误地加1，就会变成[0, 2, 2]；如果用i < p2作为循环条件，还会得到错误的[2, 0, 2]。这类小规模用例在本地复现很快，比直接提交 LeetCode 等待判题反馈更高效。

4.3 一次真实的排查过程

最后一次写这道题时，我写了个看似正确但总在某个用例上失败的版本。错误代码大概是这样的：

while i < n: 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 i += 1 # 这里错了 else: i += 1

用[2, 1, 0]测试：

初始：p0=0, p2=2, i=0。

• i=0是2，交换后数组[0, 1, 2]，p2=1，i=1（错误的 i 加1跳过检查）；
• i=1是1，i=2；
• i=2是2，交换后数组还是[0, 1, 2]，p2=0，i=3；
• 结束。

这个例子碰巧对了，但如果换成[2, 0, 2, 1]：

• i=0是2，与nums[3]=1交换，数组[1, 0, 2, 2]，p2=2，错误的 i 加1到1；
• i=1是0，与nums[0]=1交换，数组[0, 1, 2, 2]，p0=1, i=2；
• 结束？不对，i=2指向2，但这个2已经在最终位置了，不用处理。最终输出[0, 1, 2, 2]，恰好也是对的。

继续换[2, 1, 0, 2, 0]试试才能发现真正的错误。所以我的建议是：如果你发现自己那个版本怎么测都对，但心里还是不踏实，那多半是测试用例不够刁钻，多换几组人为设计过的“坏序列”再测。尤其是把2密集地放在数组中间，或者把0堆在数组末尾，最能暴露 i 在交换后是否应该自增的问题。

5. 一题撕开一片：颜色分类与三路快排、双指针家族

5.1 三路快排的 partition：75题的近亲

这道题练熟以后，再去看快速排序的“三路 partition”思路，会非常有亲切感。普通的快排 partition 将数组分成“小于pivot”和“大于等于pivot”两个区域，而三路 partition 把数组分成“小于pivot / 等于pivot / 大于pivot”三个区域，处理大量重复元素的场景时，比普通快排更高效。

看一个典型的三路 partition 代码：

def three_way_partition(nums, left, right, pivot): lt = left # 小于区的右边界 i = left # 扫描指针 gt = right # 大于区的左边界 while i <= gt: if nums[i] < pivot: nums[i], nums[lt] = nums[lt], nums[i] lt += 1 i += 1 elif nums[i] > pivot: nums[i], nums[gt] = nums[gt], nums[i] gt -= 1 else: i += 1

这里的 lt、gt、i 和颜色分类里的 p0、p2、i 几乎一一对应。pivot 就相当于是“颜色1”，小于 pivot 的相当于“颜色0”，大于 pivot 的相当于“颜色2”。所以从75题到三路快排之间只隔着一层窗户纸，把这题吃透，看三路快排代码会顺畅得多。

我在刷题群里经常看到有人问“三路快排的边界到底怎么记”，我的答案是：如果你想硬记，大概率会记混；但如果你先把75题的循环不变量画清楚，再对照着记三路快排，就会发现它俩其实是同一套逻辑换了个变量名。

5.2 双指针题型的横向对比与刷题顺序

75题练完之后，可以顺着双指针这条线继续往下刷，收益会更集中：

我的建议是先刷283，感受一下“分区”思想的最小体量；然后回来啃75题，把荷兰国旗逻辑彻底嚼碎；再去碰15题三数之和，体会双指针在更复杂场景里的应用。这样一步步上去，双指针的体系感会清晰很多，而不只是零散地背题。

如果是在面试前临时抱佛脚，那么75题至少要能手写不卡壳，并且能解释清楚：为什么遇到2交换后i不能动、循环条件为什么要i <= p2、循环不变量是什么。这三问能答利索，面试官一般就会默认为你是真正理解了，而不是背题。

最后分享一个小技巧：这道题我之后每次写快排或三路快排出问题时，都会回来翻一眼75题的荷兰国旗代码，对照 lt/gt/i 的推进节奏。很多边界 bug（比如扫描指针忘了原地等待、右边界提前收缩、循环条件差一个等号）在马里奥里就是“卡在墙边”的一种感觉，而在算法里，只要你不变量写得对，任何一步推进都不该让已经归位的元素重新回到未处理区间。刷题不必贪多，把这样一道题彻底吃透，比囫囵吞枣刷十道更有价值。