题目描述
思路解析
一句话答案：LeetCode 75 颜色分类的最优解是三指针一趟扫描，即经典的荷兰国旗问题：l 守 0 区右边界、r 守 2 区左边界、cur 居中考察，遇 0 与 l 交换后两者都前进，遇 2 与 r 交换后只收缩 r 而 cur 原地重判，遇 1 直接右移。时间 O(n)、空间 O(1)，一趟完成原地排序。
这道题真正在问什么
数组只含 0、1、2 三种值，要求原地按 0、1、2 的顺序排好，不许调库排序，并且最好一趟扫描完成。值域只有三个，套通用排序是杀鸡用牛刀——真正的考点是利用「只有三类」这个信息，把排序退化成「分区」：把每个数直接归进它所属的区域。这就是经典的荷兰国旗问题。
计数排序为什么还不够好
最直观的做法是计数排序：第一趟数出 0、1、2 各有几个，第二趟按个数把数组重新填一遍。它同样是 O(n) 时间、O(1) 空间，逻辑最简单，但要扫两趟。当题目或面试官追问「能不能只扫一趟」时，就需要边扫边把每个数当场放进正确的区域——这正是三指针的用武之地。
三个指针各自守住什么不变量
l 指向 0 区右侧的第一个空位，r 指向 2 区左侧的第一个空位，cur 是当前考察位置。全程保持四段结构：l 左边全是 0，l 到 cur 之间全是 1，cur 到 r 是尚未考察的未知区，r 右边全是 2。cur 每看一个数就把它归位：是 0 就和 l 交换（0 区长一格），是 2 就和 r 交换（2 区长一格），是 1 就正好留在中段、直接右移。当 cur 越过 r，未知区清空，三段区域收拢相接，数组自然有序——正确性全靠这组不变量每一步都不被破坏。
为什么遇 2 交换后 cur 不能前进
这是全题最关键的不对称。和 r 交换时，换过来的数来自右侧的未知区，可能是 0、1、2 中任何一个、还没被考察过，所以 cur 必须留在原地对新来的值再判一次，否则一个 0 可能被漏在中间。而和 l 交换时不同：l 始终不超过 cur，l 位置上的数属于已处理区域，只能是 1（或者 l 与 cur 重合时的自换），换过来不需要重判，cur 可以放心前进。可以这样记：从左边换来的是旧相识，从右边换来的是陌生人，陌生人必须重新过一遍安检。
复杂度与最容易踩的两个坑
cur 与 r 相向而行，合计把数组扫一遍，时间 O(n)；只用三个下标变量，原地交换，空间 O(1)。两个高频坑：一是循环条件必须写 cur <= r 而不是 cur < n——r 右边已经是排好的 2 区，越过 r 继续处理会把排好的 2 再换乱；二是遇 0 交换后忘了让 cur 前进——l 与 cur 重合时交换前后值不变，cur 不前进就会永远停在原地死循环。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这句「0 扔左边（和 l 换）、2 扔右边（和 r 换）、1 留中间；遇 2 换完 cur 别急着走」，下面每帧都在套它。
cur 处看到的是 2。2 该待在最右边，所以准备把它和 r（下标 13，2 区左侧第一个空位）处的值交换。这一帧先点亮 cur 与 r，还没动手。
交换完成：2 落进下标 13，右边的「2 区」又长一格，r 左移收缩。注意 cur 没动——从 r 换过来的值还没看过，下一帧得在原地再判一次它是 0/1/2。这是本题唯一反直觉的点。
cur 处看到的是 2。2 该待在最右边，所以准备把它和 r（下标 12，2 区左侧第一个空位）处的值交换。这一帧先点亮 cur 与 r，还没动手。
交换完成：2 落进下标 12，右边的「2 区」又长一格，r 左移收缩。注意 cur 没动——从 r 换过来的值还没看过，下一帧得在原地再判一次它是 0/1/2。这是本题唯一反直觉的点。
cur 处看到的是 1。1 本来就该待在中间，什么都不用做，cur 直接右移看下一个。l 和 r 都不动。
cur 处看到的是 0。0 该待在最左边，所以准备把它和 l（下标 0，0 区右侧第一个空位）处的值交换。这一帧先点亮 cur 与 l，还没动手。
交换完成：0 落进下标 0，左边的「0 区」又长了一格。因为从 l 换来的值是之前已看过的（必是 1 或就地），所以 l 和 cur 都往右前进一格，继续往下扫。
cur 处看到的是 2。2 该待在最右边，所以准备把它和 r（下标 11，2 区左侧第一个空位）处的值交换。这一帧先点亮 cur 与 r，还没动手。
交换完成：2 落进下标 11，右边的「2 区」又长一格，r 左移收缩。注意 cur 没动——从 r 换过来的值还没看过，下一帧得在原地再判一次它是 0/1/2。这是本题唯一反直觉的点。
cur 处看到的是 0。0 该待在最左边，所以准备把它和 l（下标 1，0 区右侧第一个空位）处的值交换。这一帧先点亮 cur 与 l，还没动手。
交换完成：0 落进下标 1，左边的「0 区」又长了一格。因为从 l 换来的值是之前已看过的（必是 1 或就地），所以 l 和 cur 都往右前进一格，继续往下扫。
cur 处看到的是 1。1 本来就该待在中间，什么都不用做，cur 直接右移看下一个。l 和 r 都不动。
cur 处看到的是 1。1 本来就该待在中间，什么都不用做，cur 直接右移看下一个。l 和 r 都不动。
cur 处看到的是 0。0 该待在最左边，所以准备把它和 l（下标 2，0 区右侧第一个空位）处的值交换。这一帧先点亮 cur 与 l，还没动手。
交换完成：0 落进下标 2，左边的「0 区」又长了一格。因为从 l 换来的值是之前已看过的（必是 1 或就地），所以 l 和 cur 都往右前进一格，继续往下扫。
cur 处看到的是 1。1 本来就该待在中间，什么都不用做，cur 直接右移看下一个。l 和 r 都不动。
cur 处看到的是 2。2 该待在最右边，所以准备把它和 r（下标 10，2 区左侧第一个空位）处的值交换。这一帧先点亮 cur 与 r，还没动手。
交换完成：2 落进下标 10，右边的「2 区」又长一格，r 左移收缩。注意 cur 没动——从 r 换过来的值还没看过，下一帧得在原地再判一次它是 0/1/2。这是本题唯一反直觉的点。
cur 处看到的是 2。2 该待在最右边，所以准备把它和 r（下标 9，2 区左侧第一个空位）处的值交换。这一帧先点亮 cur 与 r，还没动手。
交换完成：2 落进下标 9，右边的「2 区」又长一格，r 左移收缩。注意 cur 没动——从 r 换过来的值还没看过，下一帧得在原地再判一次它是 0/1/2。这是本题唯一反直觉的点。
cur 处看到的是 1。1 本来就该待在中间，什么都不用做，cur 直接右移看下一个。l 和 r 都不动。
cur 处看到的是 0。0 该待在最左边，所以准备把它和 l（下标 3，0 区右侧第一个空位）处的值交换。这一帧先点亮 cur 与 l，还没动手。
交换完成：0 落进下标 3，左边的「0 区」又长了一格。因为从 l 换来的值是之前已看过的（必是 1 或就地），所以 l 和 cur 都往右前进一格，继续往下扫。
cur 越过了 r，一趟扫描结束：左边一段全是 0、中间全是 1、右边全是 2，结果 [0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]。三个指针合起来只把数组走了一遍，O(n) 时间、O(1) 额外空间。
边界先想清：全同色时退化成「指针各自走到头」，结果不变。
两个高频追问：区分两趟计数排序与一趟三指针，并讲清「为什么遇 0 能走、遇 2 不能走」。
参考代码
def sortColors(nums): l, cur, r = 0, 0, len(nums) - 1 # 0区右界 / 当前 / 2区左界 while cur <= r: if nums[cur] == 0: # 0 扔左边 nums[l], nums[cur] = nums[cur], nums[l] l += 1; cur += 1 elif nums[cur] == 2: # 2 扔右边 nums[cur], nums[r] = nums[r], nums[cur] r -= 1 # cur 不动! else: # 1 留中间 cur += 1复杂度
- 时间：O(n)，cur 与 r 相向，合计只扫一遍
- 空间：O(1)，只用三个指针，原地交换，不开新数组
易错点
面试追问把动画讲成自己的话
追问不用三指针，最直观的解法是什么？有什么缺点？
追问为什么遇 0 交换后 cur 能直接前进，遇 2 却不能？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最接近的三数之和
LeetCode 16 · 中等 · 沿着 双指针 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题