LeetCode 75：颜色分类（荷兰国旗问题）—— Java 题解 ✅
🔗 题目链接
👉 https://leetcode.cn/problems/sort-colors/
📖 内容概要
给定一个只包含0、1、2的数组nums，要求原地排序，使得相同颜色相邻，并按0 → 1 → 2顺序排列。
本题本质是荷兰国旗问题（Dutch National Flag Problem），要求一次遍历、常数空间完成排序。
💡 解题思路（重点）
核心思想：三指针一次遍历
我们将数组划分为四个区间：
[0 ... l-1] → 全是 0 [l ... i-1] → 全是 1 [i ... r] → 未处理 [r+1 ... n-1] → 全是 2三个指针含义
| 指针 | 含义 |
|---|---|
l | 下一个放0的位置 |
r | 下一个放2的位置 |
i | 当前遍历指针 |
遍历规则（非常关键）
当遍历到nums[i]时：
✅ 情况 1：nums[i] == 0
- 说明当前元素应该去左边
- 交换
nums[i]和nums[l] l++、i++
👉为什么i++？
- 因为换过来的数一定是
1（已处理过）
✅ 情况 2：nums[i] == 2
- 说明当前元素应该去右边
- 交换
nums[i]和nums[r] r--- ⚠️ 不移动
i
👉为什么i不动？
- 换过来的数还没检查过（可能是 0 / 1 / 2）
✅ 情况 3：nums[i] == 1
- 已经在正确位置
- 直接
i++
终止条件
while(i<=r)当i超过r，说明所有元素都已分区完成。
✅ AC 代码（Java）
classSolution{publicvoidsortColors(int[]nums){intl=0,r=nums.length-1;inti=0;while(i<=r){if(nums[i]==0){swap(nums,i,l);i++;l++;}elseif(nums[i]==2){swap(nums,i,r);r--;}else{i++;}}}privatevoidswap(int[]nums,inta,intb){inttmp=nums[a];nums[a]=nums[b];nums[b]=tmp;}}⏱️ 复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间复杂度 | O(n)（一次遍历） |
| 空间复杂度 | O(1)（原地排序） |
✅ 总结
- 本题是经典的数组双指针 / 三指针问题
- 核心在于理解指针不移动的原因
- 是面试中高频出现的原地排序技巧
✅ 一次遍历
✅ 不使用额外空间
✅ 逻辑紧凑，代码优雅
