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] → 未处理 [r1 ... n-1] → 全是 2三个指针含义指针含义l下一个放0的位置r下一个放2的位置i当前遍历指针遍历规则非常关键当遍历到nums[i]时✅ 情况 1nums[i] 0说明当前元素应该去左边交换nums[i]和nums[l]l、i为什么i因为换过来的数一定是1已处理过✅ 情况 2nums[i] 2说明当前元素应该去右边交换nums[i]和nums[r]r--⚠️ 不移动i为什么i不动换过来的数还没检查过可能是 0 / 1 / 2✅ 情况 3nums[i] 1已经在正确位置直接i终止条件while(ir)当i超过r说明所有元素都已分区完成。✅ AC 代码JavaclassSolution{publicvoidsortColors(int[]nums){intl0,rnums.length-1;inti0;while(ir){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){inttmpnums[a];nums[a]nums[b];nums[b]tmp;}}⏱️ 复杂度分析指标复杂度时间复杂度O(n)一次遍历空间复杂度O(1)原地排序✅ 总结本题是经典的数组双指针 / 三指针问题核心在于理解指针不移动的原因是面试中高频出现的原地排序技巧✅ 一次遍历✅ 不使用额外空间✅ 逻辑紧凑代码优雅