75. 颜色分类（Sort Colors）
频次 ★★★★ · 难度 🟡 · 高频：字节/腾讯
题目
数组只含 0、1、2（红白蓝），原地一趟排序，不许用库函数。
示例：
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
思路
荷兰国旗问题，三指针分区：
p0：0 区右边界（下一个 0 该放的位置）p2：2 区左边界（下一个 2 该放的位置）i：当前扫描位置
nums[i] 为 0 → 与 p0 交换，p0++、i++；为 2 → 与 p2 交换，p2—，i 不动（换来的元素还没检查）；为 1 → i++。当 i > p2 时三区闭合。
代码
public void sortColors(int[] nums) {
int p0 = 0, i = 0, p2 = nums.length - 1;
while (i <= p2) {
if (nums[i] == 0) swap(nums, i++, p0++); // 换来的必是 1(i 走过的区域),可前进
else if (nums[i] == 2) swap(nums, i, p2--); // 换来的未检查,i 停住
else i++;
}
}复杂度
- 时间：O(n) 一趟
- 空间：O(1)
边界条件
- 全同色：与自身交换或直接扫过，正常结束
- 长度 1：循环一次即出
- 已有序：0 与 p0 自交换，i 与 p0 同步走
变式
- 计数排序两趟版：数 0/1/2 个数再回填——两趟且需改写值，一趟三指针是本题考点
- 推广到 k 种颜色：三指针不再够用，退回计数排序 O(n+k)
易错点
- 与 p2 交换后 i 不能前进——换回来的可能是 0 或 2，没检查过；与 p0 交换后 i 可以前进，因为 p0 ≤ i，p0 位置的值是 i 已经扫过的（只能是 1）
- 循环条件
i <= p2不是i < n——p2 右边已是成品区，多扫会把 2 再换回来 - 三个分支必须互斥完整，别把
else if写成两个if（交换后值变了会连做两个分支）
面试追问
- 为什么与 p0 换完 i 能走、与 p2 换完不能？ 这就是本题唯一的坑：p0 一侧换来的元素来自”i 已扫过区”，必为 1；p2 一侧来自”未扫描区”。答清楚这条不变量，这题就过了
- 和快排的关系？ 三指针分区就是快排的三路划分（partition3），处理大量重复键时避免退化，见数据结构与算法排序部分