颜色分类
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1
示例 2
模拟答题者思考
1. 暴力：复制数组后按 0、1、2 计数再写回——O(n) 时间但用了 O(n) 额外空间；或冒泡/选择排序——O(n²)，都不满足「常数空间一趟扫描」的进阶要求。
2. 重复在哪里？只有三种取值，目标是把数组切成三段 0 | 1 | 2。若用两次扫描：先数出 c0、c1、c2 再按顺序覆写，逻辑清晰且 O(n) 时间 O(1) 空间——可作为基线，但还想再优化成单趟。
3. 荷兰国旗（三指针）：维护 0 区、1 区、2 区的边界。用 p1 从左扫，遇到 0 换到 p0 并扩 0 区；遇到 1 直接归入 1 区；遇到 2 换到 p2 并缩未处理区间——换下来的数可能仍是 0/1/2，所以换 2 时不能盲目 p1++。
4. 例 [2,0,2,1,1,0]：p1 遇 2 与尾部 0 交换得到 [0,0,2,1,1,2]，再处理两个 0 扩 0 区，中间 1 自然落在 p0..p1-1，最后 2 全在右端。
5. 循环条件 p1 <= p2：当 p1 越过 p2 时三段已划分完毕。每个元素最多被交换常数次，时间 O(n)，仅用三个下标 O(1) 空间。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
p0 | int | 定义：下一段「待写入 0」的起始下标；恒有 nums[0..p0-1] == 0维护：初始 p0 = 0；每确认一个 0 就扩展 0 区并右移边界更新：当 nums[p1] == 0 时与 nums[p0] 交换，然后 p0 += 1 |
p1 | int | 定义：当前扫描指针，处理区间 [p1, p2] 内尚未归类的元素维护：恒有 nums[p0..p1-1] == 1（1 区紧挨 0 区之后）更新：见 nums[p1] 为 0 则换到 p0 并 p0++、p1++；为 1 则仅 p1++；为 2 则与 p2 交换并 p2--（p1 不动，换入元素待再看） |
p2 | int | 定义：下一段「已确定为 2」的左边界；恒有 nums[p2+1..n-1] == 2维护：初始 p2 = n - 1；扫描过程中 2 不断被换到数组尾部更新：当 nums[p1] == 2 时与 nums[p2] 交换，然后 p2 -= 1 |
落码步骤
1. 令 n = len(nums)，p0 = 0、p1 = 0、p2 = n - 1
2. 当 p1 <= p2：若 nums[p1] == 0，交换 nums[p0] 与 nums[p1]，p0 += 1、p1 += 1
3. 若 nums[p1] == 1，仅 p1 += 1
4. 若 nums[p1] == 2，交换 nums[p1] 与 nums[p2]，p2 -= 1（p1 不变）
5. 循环结束，nums 已按 0、1、2 有序（函数无返回值，原地修改）
代码实现
class Solution:
def sortColors(self, nums: list[int]) -> None:
p0 = p1 = 0
p2 = len(nums) - 1
while p1 <= p2:
if nums[p1] == 0:
nums[p0], nums[p1] = nums[p1], nums[p0]
p0 += 1
p1 += 1
elif nums[p1] == 1:
p1 += 1
else:
nums[p1], nums[p2] = nums[p2], nums[p1]
p2 -= 1class Solution {
public:
void sortColors(vector<int>& nums) {
int p0 = 0, p1 = 0, p2 = (int)nums.size() - 1;
while (p1 <= p2) {
if (nums[p1] == 0) {
swap(nums[p0], nums[p1]);
p0++;
p1++;
} else if (nums[p1] == 1) {
p1++;
} else {
swap(nums[p1], nums[p2]);
p2--;
}
}
}
};
// 时间 O(n)，空间 O(1)复杂度分析
O(n)
O(1)
常见坑
遇到 2 与 p2 交换后不要 p1++：换到 p1 的可能是 0 或 1，必须下一轮再判断。
遇到 0 时若只 p1++ 不交换、不移动 p0，0 会留在中间，三段 invariant 被破坏。
循环条件是 p1 <= p2 而非 p1 < n：右端 2 区已归位，继续扫会重复处理已确定的 2。
必测边界 Case
nums = [1] → [1]
nums = [0,0,1,1,2,2] → 不变（p1 一路递增，无多余交换）
nums = [2,1,0] → [0,1,2]（多次交换仍在一趟内完成）
nums = [2,2,2] → [2,2,2]（p2 不断左移，p1 始终为 0）