颜色分类与荷兰国旗问题：双指针一次遍历的经典进阶

看一眼标题很多人可能会觉得“颜色分类”又是一道基础的排序题直接调排序函数或者数一数0、1、2的个数就完事了。但真正把这题吃透的人都知道75题是双指针进阶的一个经典入口——它背后是荷兰国旗问题是后面理解三路快排、循环不变量、双指针调度逻辑的最佳跳板。这篇文章就把我从“暴力解”到“一次遍历双指针”的完整思路、代码细节、踩坑点以及延伸题都捋一遍希望能帮你把这题彻底放进自己的知识体系里。1. 粗看是排序细看是分区先吃透题目真正想考什么1.1 题面拆解与定位原题给了一个只包含0、1、2的整数数组0代表红色、1代表白色、2代表蓝色要求原地排序让相同颜色的元素相邻并且按红、白、蓝的顺序排列。看起来是排序但仔细想想这题的核心不是“排序算法”而是“分区”——把一个无序的三色数组按照固定顺序划分成三个连续区间。面试和刷题里遇到它最常见的考核点是三个递进层次你能不能在不调用排序库的情况下完成能不能做到常数空间也就是原地操作能不能做到只扫描一遍数组把时间复杂度和空间复杂度同时压到最优。大部分人的第一反应是先统计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之间全都是1nums[p0]只可能是1或者在i p0时是当前这个0自己和自己交换结果不变所以交换后 i 位置的元素必定是1或0可以直接推进。这一个区别就是整个算法最容易翻车的地方。2.2 循环不变量与边界条件写成正式一点的循环不变量大概是这样的区间[0, p0)内的元素全是0区间[p0, i)内的元素全是1区间(p2, len(nums)-1]内的元素全是2区间[i, p2]内的元素是尚未处理的未知元素。循环开始时p00、i0、p2n-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]。初始p00, p25, i0数组原样。i0元素是2和nums[5]交换数组变成[0, 0, 2, 1, 1, 2]p24i 仍为0i0元素是0和nums[0]交换自己换自己数组不变p01, i1i1元素是0和nums[1]交换自己换自己数组不变p02, i2i2元素是2和nums[4]交换数组变成[0, 0, 1, 1, 2, 2]p23i 仍为2i2元素是1i3i3循环条件i p23 3成立元素是1i4现在i4 p23退出循环。最终数组是[0, 0, 1, 1, 2, 2]符合要求。注意最后一次循环i3和p23指向同一个元素这个元素是我们把原来i2位置的2换走之后留下的“未知元素”也就是原p2位置的值它恰好是1。把它处理后未知区间才真正清空。如果循环条件是i p2这一步就会被跳过最后的1就漏掉了。3.2 最容易写错的几个分支这里我汇总一下刷这道题时大家最容易写错的细节易错点错误写法后果遇到2交换后 i 直接加1nums[i], nums[p2] nums[p2], nums[i]; p2 - 1; i 1换回来的新元素没检查可能漏掉0或2遇到0交换后 i 忘记加1交换后只更新 p0不前进 i无限循环或重复处理同一个0循环条件写成 i n左侧正确但 i 会进入已排好的2区域可能把右侧的2换回中间导致排序失败循环条件写成 i p2最后一个未知元素i p2 时漏处理中间区域残留未分类元素只维护 p0 和 p2不维护 i 的语义处理2后 i 语义混淆不变量被破坏结果不稳定我自己的做题经验是把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]测试初始p00, p22, i0。i0是2交换后数组[0, 1, 2]p21i1错误的 i 加1跳过检查i1是1i2i2是2交换后数组还是[0, 1, 2]p20i3结束。这个例子碰巧对了但如果换成[2, 0, 2, 1]i0是2与nums[3]1交换数组[1, 0, 2, 2]p22错误的 i 加1到1i1是0与nums[0]1交换数组[0, 1, 2, 2]p01, i2结束不对i2指向2但这个2已经在最终位置了不用处理。最终输出[0, 1, 2, 2]恰好也是对的。继续换[2, 1, 0, 2, 0]试试才能发现真正的错误。所以我的建议是如果你发现自己那个版本怎么测都对但心里还是不踏实那多半是测试用例不够刁钻多换几组人为设计过的“坏序列”再测。尤其是把2密集地放在数组中间或者把0堆在数组末尾最能暴露 i 在交换后是否应该自增的问题。5. 一题撕开一片颜色分类与三路快排、双指针家族5.1 三路快排的 partition75题的近亲这道题练熟以后再去看快速排序的“三路 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. 移动零只分0和非0两区是75题的特例只需要一个指针维护0区边界非0区不需要二次排序27. 移除元素双指针覆盖旧值需要保留非移除值的相对顺序26. 删除有序数组中的重复项快慢指针维护“合法前缀”只关注相邻重复不涉及交换11. 盛最多水的容器左右指针相向而行指针移动的依据不是元素分类而是面积计算15. 三数之和排序后双指针夹逼需要去重边界条件更繁杂我的建议是先刷283感受一下“分区”思想的最小体量然后回来啃75题把荷兰国旗逻辑彻底嚼碎再去碰15题三数之和体会双指针在更复杂场景里的应用。这样一步步上去双指针的体系感会清晰很多而不只是零散地背题。如果是在面试前临时抱佛脚那么75题至少要能手写不卡壳并且能解释清楚为什么遇到2交换后i不能动、循环条件为什么要i p2、循环不变量是什么。这三问能答利索面试官一般就会默认为你是真正理解了而不是背题。最后分享一个小技巧这道题我之后每次写快排或三路快排出问题时都会回来翻一眼75题的荷兰国旗代码对照 lt/gt/i 的推进节奏。很多边界 bug比如扫描指针忘了原地等待、右边界提前收缩、循环条件差一个等号在马里奥里就是“卡在墙边”的一种感觉而在算法里只要你不变量写得对任何一步推进都不该让已经归位的元素重新回到未处理区间。刷题不必贪多把这样一道题彻底吃透比囫囵吞枣刷十道更有价值。