75. 颜色分类

难度：🟡 Medium | 标签：三指针、荷兰国旗 | 状态：⬜ LeetCode 链接

思路

三指针 l / mid / r：

• l 之前都是 0
• r 之后都是 2
• [l, mid) 都是 1

mid 扫，遇到 0 与 l swap 并都 ++；遇到 2 与 r swap 并 r—（mid 不动，因为换来的可能还是 0/2）；遇到 1 mid++。

代码

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int l = 0, mid = 0, r = nums.size() - 1;
        while (mid <= r) {
            if (nums[mid] == 0)      swap(nums[l++], nums[mid++]);
            else if (nums[mid] == 2) swap(nums[mid], nums[r--]);
            else                     ++mid;
        }
    }
};

复杂度

• 时间 O(n)，空间 O(1)

易错 / 回顾

• 遇 2 swap 后 mid 不动（换过来的值未检查）
• 遇 0 时 l 和 mid 都 ++（换过来的是 1，无需再检）
• 循环条件 mid <= r，不是 <