颜色分类 图解题解
三种颜色一趟排好，三个指针各司其职，不用计数也不用两遍扫。
像分拣传送带上的红中蓝三色球：l 左边专门堆红球（0），r 右边专门堆蓝球（2），i 是当前检查位。i 遇蓝就和 r 换、r 往左收——换来的球还没看过，i 原地重判；遇红就和 l 换、l 和 i 一起往右走；遇中就 i 直接前进。i 追上 r，三色全就位，一趟完事。
这道题到底在问什么
- nums
- [2, 0, 2, 1, 1, 0]
- 输出
- [0, 0, 1, 1, 2, 2]
最优解：一步一步想明白
- 3最直接是计数排序：第一趟数出 0、1、2 各几个，第二趟按数量从头重填。结果对，但要扫两趟。题目只有三种值，其实一趟就能就地分好——这正是三指针的用武之地。
- 4关键招：l 左边全是已就位的 0，r 右边全是已就位的 2，i 是当前检查位。i 遇 0 就和 l 换、l 和 i 一起前进；遇 2 就和 r 换、r 后退但 i 留在原地；遇 1 就 i 直接前进。i 越过 r 就排完——一趟、原地。
- 5l＝0，i＝0，r＝5三个指针就位：l 和 i 都从最左边出发，r 在最右边。i 负责逐个检查，l 把 0 推到左段、r 把 2 推到右段。
- 6和 r 交换，r 后退到 4当前是 2，和 r（下标 5）交换，r 退到 4。注意 i 不前进——换过来的是个 0，还没检查过，下一步要在原地重判它。
- 7和 l 交换，l、i 前进到 1重判 i＝0：换过来的正是 0，和 l（下标 0）交换，其实是自己跟自己换。l 和 i 都前进到 1，下标 0 锁定为红色 0，变灰。
- 8和 l 交换，l、i 前进到 2又是 0，和 l（下标 1）交换，l 和 i 都前进到 2。左边已是 [0, 0] 两个就位的红色。
- 9和 r 交换，r 后退到 3当前是 2，和 r（下标 4）交换，r 退到 3。i 仍然不动，换来的 1 还要再判一次。
- 10i 前进到 3重判 i＝2：换过来是 1，本就该在中间，不交换，i 直接前进到 3。
- 11i＝4 大于 r＝3，停又是 1，不交换，i 前进到 4。此时 i 越过了 r（4 大于 3），r 右边的 [2, 2] 早已就位，扫描结束。
- 12[0,0,1,1,2,2]一趟扫描完成排序：l 左边全 0、r 右边全 2、中间全 1，得到 [0, 0, 1, 1, 2, 2]。
- 13[0,l) 全 0 · [l,i) 全 1 · (r,末] 全 2 · [i,r] 待定慢放看清四段：l 左边全是 0、i 左边到 l 之间全是 1、r 右边全是 2，只有 i 到 r 之间还没看。每动一步，这四段的边界都严格成立——这就是荷兰国旗的不变量。
- 16l 守左段全 0、r 守右段全 2，中间 [l, i) 是已确定的 1、[i, r] 是待处理区——这就是分区思想，快排的 partition 也是同一招。
- 18错误写法：i 跟着 r 一起动用本例演一遍错法：i＝0 遇 2，和 r 换后 [0,0,2,1,1,2]。如果 i 也跟着前进到 1，那个刚换来的 0 就被跳过，l 再也碰不到它，最后下标 0 卡着个本该归左的 0——结果排错。所以遇 2 后 i 必须原地。
- 19空 → 单元素 → 全相同三个边界都不崩：空数组 r＝-1，i 小于等于 r 直接为假、循环一次都不进。单元素 nums＝[2]，i＝0、r＝0 进一次换自己、r 退到 -1 就停。全相同 [1,1,1] 全走中间分支、i 扫到底即可。
- 23把这题练到能复述后再迁移：LC283 移动零是「两段分区」（非零 / 零），快排 partition 是「小于基准 / 大于基准」两段，本题是三段——都是同一套「指针守边界、扫描归位」的分区思想。去数组专题里把它们串起来，再用师兄答疑追问「为什么 i 有时不动」。
⚠️ 容易写错的地方
✗ 错：遇到 2 和 r 交换后 i 也一起前进
✓ 对：遇到 2 交换后只 r 后退，i 留在原地重判
从 r 换来的数还没检查过，可能是 0（本例 i＝0 换来的就是 0），i 一前进就漏判，那个 0 永远到不了左段
✗ 错：while i 小于 len(nums)
✓ 对：while i 小于等于 r
r 右边已全是就位的 2，i 越过 r 就该停，再扫只会把排好的 2 又换乱
✗ 错：遇到 0 时只交换、忘了 i 也加 1
✓ 对：遇到 0 时 l 和 i 同步加 1
和 l 换来的数来自 [l, i) 区间、那里已全是 1，换到 i 位置后已确定、无需再看，所以 i 必须跟着前进；不进会死循环
完整代码（Python / C++ / Java）
Python
class Solution:
def sortColors(self, nums):
l, i, r = 0, 0, len(nums) - 1
while i <= r:
if nums[i] == 0:
nums[l], nums[i] = nums[i], nums[l]
l += 1
i += 1
elif nums[i] == 2:
nums[r], nums[i] = nums[i], nums[r]
r -= 1 # i 不动!
else:
i += 1C++
class Solution {
public:
void sortColors(vector<int>& nums) {
int l = 0, i = 0, r = nums.size() - 1;
while (i <= r) {
if (nums[i] == 0) swap(nums[l++], nums[i++]);
else if (nums[i] == 2) swap(nums[r--], nums[i]);
else i++;
}
}
};Java
class Solution {
public void sortColors(int[] nums) {
int l = 0, i = 0, r = nums.length - 1;
while (i <= r) {
if (nums[i] == 0) { int t = nums[l]; nums[l++] = nums[i]; nums[i++] = t; }
else if (nums[i] == 2) { int t = nums[r]; nums[r--] = nums[i]; nums[i] = t; }
else i++;
}
}
}套路模板 · 三指针分区（挖空骨架，背判据）
# 三指针分区骨架：l 守左段、r 守右段、i 扫描
l, i, r = 0, 0, n - 1
while i <= r: # i 越过 r 即停
if 该放左段(nums[i]): # 例: nums[i]==0
swap(l, i); l += 1; i += 1 # 左段已扫过 → i 跟进
elif 该放右段(nums[i]): # 例: nums[i]==2
swap(r, i); r -= 1 # 右段没扫过 → i 不动!
else:
i += 1 # 留中段，直接走// 把「该放左段 / 该放右段」换成本题判据即可复用
int l = 0, i = 0, r = n - 1;
while (i <= r) {
if (goLeft(nums[i])) { swap(nums[l++], nums[i++]); } // i 跟进
else if (goRight(nums[i])) { swap(nums[r--], nums[i]); } // i 不动!
else i++;
}// 判据替换: goLeft / goRight 改成本题条件
int l = 0, i = 0, r = n - 1;
while (i <= r) {
if (goLeft(nums[i])) { swap(nums, l++, i++); } // i 跟进
else if (goRight(nums[i])) { swap(nums, r--, i); } // i 不动!
else i++;
}复杂度
时间复杂度
O(n)
每轮要么 i 前进、要么 r 后退，i 和 r 相向而行最多走 n 步
空间复杂度
O(1)
只用 l、i、r 三个下标，原地交换、不开计数数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 颜色分类 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么不用 sort，非要三指针?+
题目要求不用库排序、且最好一趟原地完成。利用「只有三种值」这个强约束，三指针 O(n) 一趟、O(1) 空间，优于通用排序的 O(n log n)。
和计数排序比有什么优劣?+
计数排序也是 O(n)、O(1)，但要扫两趟（先数后填）。三指针只扫一趟，且是真正的原地交换；面试官常追问「能否一趟」时就是想要这个。
遇 0 和 l 换、遇 2 和 r 换，为什么处理方式不对称?+
因为 l 左边的数 i 早扫过、是 1，换来的已确定，i 可前进；而 r 右边的数 i 还没扫过，换来的未知，i 必须留下重判。不对称正是这道题的精华。
如果值不止三种、要分成 k 段呢?+
三指针专吃「三类」这个约束，推广到 k 类就退化了，一般改用计数排序或基于比较的排序。荷兰国旗是「恰好三分」的特解。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。