LeetCode Hot 100：颜色分类 (2026)

本期讲 LeetCode Hot 100 的「颜色分类」。它来自 LeetCode 热题 100 题单，原题是力扣 75. 颜色分类。题目给一个只包含 0、1、2 的数组 nums，要求原地排序成 [0...0, 1...1, 2...2]，不能调用内置 sort；进阶要求是常数空间的一趟扫描。

这题的核心不是排序，而是三段不变量：left 左边全是 0，right 右边全是 2，i 扫描中间未知区。遇到 0，交换到 left，然后 left 和 i 都右移；遇到 2，交换到 right，只让 right 左移，i 留在原地继续检查换回来的数。

function sortColors(nums) {
  let left = 0;
  let i = 0;
  let right = nums.length - 1;

while (i <= right) {
    if (nums[i] === 0) {
      [nums[left], nums[i]] = [nums[i], nums[left]];
      left++;
      i++;
    } else if (nums[i] === 1) {
      i++;
    } else {
      [nums[i], nums[right]] = [nums[right], nums[i]];
      right--;
    }
  }
}

时间复杂度是 O(n)，因为 i 只向右扫描，right 只向左收缩；额外空间复杂度是 O(1)。边界上，数组长度最小为 1，值只会是 0、1、2，所以不用额外处理其他数字。

Related content