LeetCode 75：颜色分类（荷兰国旗问题）—— Java 题解 ✅

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

三个指针含义

遍历规则（非常关键）

当遍历到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;}}

⏱️ 复杂度分析

✅ 总结

• 本题是经典的数组双指针 / 三指针问题
• 核心在于理解指针不移动的原因
• 是面试中高频出现的原地排序技巧

✅ 一次遍历
✅ 不使用额外空间
✅ 逻辑紧凑，代码优雅