力扣三题精解：双指针与数组操作实战-育师

1. 力扣三题精解：颜色分类、下一个排列与寻找重复数

刷算法题是程序员提升基本功的必经之路，而力扣（LeetCode）作为全球知名的编程题库，其题目质量与分类体系深受开发者认可。今天我想分享三道中等难度的经典题目：75.颜色分类、31.下一个排列和287.寻找重复数。这三题分别考察了双指针技巧、数组排列规律和环形链表检测思想，都是面试中的高频考点。

我在实际刷题过程中发现，这三道题虽然表面看起来毫不相关，但背后都隐藏着对数组操作的深刻理解。掌握它们不仅能帮助你在面试中游刃有余，更能提升对基础数据结构的敏感度。下面我将从问题分析、解法思路到具体实现，一步步拆解这三道题目，并分享一些只有实际编码才能获得的经验技巧。

2. 75.颜色分类：荷兰国旗问题实战

2.1 问题重述与初步分析

题目要求我们原地对一个只包含0、1、2的数组进行排序，使得所有0排在前面，1在中间，2在最后。这其实就是著名的荷兰国旗问题（Dutch National Flag Problem），由计算机科学家Edsger Dijkstra提出。

关键约束条件：

必须原地排序（空间复杂度O(1)）
只能遍历数组一次（时间复杂度O(n)）
不能使用库的排序函数

注意：原地排序意味着不能使用额外空间创建新数组，这对算法设计提出了更高要求。

2.2 双指针解法详解

最优雅的解法是使用三指针技巧，这也是面试官最希望看到的解决方案。具体思路如下：

初始化三个指针：
- left：指向当前0的右边界（初始为0）
- right：指向当前2的左边界（初始为len(nums)-1）
- current：当前遍历指针（初始为0）
遍历规则：
- 当nums[current] == 0：与left交换，left++，current++
- 当nums[current] == 1：直接current++
- 当nums[current] == 2：与right交换，right--（注意此时不移动current）

def sortColors(nums): left, current, right = 0, 0, len(nums) - 1 while current <= right: if nums[current] == 0: nums[left], nums[current] = nums[current], nums[left] left += 1 current += 1 elif nums[current] == 1: current += 1 else: nums[current], nums[right] = nums[right], nums[current] right -= 1

2.3 关键点与易错分析

指针移动的边界条件：
- 与left交换后可以安全地移动current，因为left指向的元素已经被处理过
- 但与right交换后不能移动current，因为从右边交换过来的元素尚未被检查
时间复杂度分析：
- 每个元素最多被交换两次（一次到左边，一次到右边）
- 总体时间复杂度严格O(n)
常见错误：
- 忘记处理current > right的终止条件
- 在交换2之后错误地移动current指针
- 边界条件处理不当导致数组越界

3. 31.下一个排列：字典序排列的奥秘

3.1 排列的数学定义

"下一个排列"指的是在当前排列的字典序中，比当前排列大的最小排列。例如：

1,2,3 → 1,3,2
3,2,1 → 1,2,3（因为是循环的）

理解字典序的关键是认识到排列可以看作一个数字，下一个排列就是"比当前数字大的最小数字"。

3.2 算法步骤拆解

解决这个问题的标准算法步骤如下：

从后向前查找第一个降序对：找到第一个满足nums[i] < nums[i+1]的i
如果找不到，说明已经是最大排列，直接反转整个数组
否则，从后向前找到第一个大于nums[i]的元素nums[j]
交换nums[i]和nums[j]
反转i+1到末尾的部分

def nextPermutation(nums): n = len(nums) i = n - 2 while i >= 0 and nums[i] >= nums[i+1]: i -= 1 if i >= 0: j = n - 1 while j >= 0 and nums[j] <= nums[i]: j -= 1 nums[i], nums[j] = nums[j], nums[i] left, right = i+1, n-1 while left < right: nums[left], nums[right] = nums[right], nums[left] left += 1 right -= 1

3.3 实战技巧与注意事项

为什么从后向前查找：
- 字典序的变化总是从低位开始
- 这样可以确保找到的是"最小"的更大排列
反转而不是排序：
- 在找到i之后，i+1到末尾的部分一定是降序的
- 反转这部分可以达到升序效果，且时间复杂度O(n)优于排序的O(nlogn)
边界情况处理：
- 空数组或单元素数组直接返回
- 全降序数组需要特殊处理

4. 287.寻找重复数：龟兔赛跑的精妙应用

4.1 问题描述与约束

给定一个包含n+1个整数的数组nums，其中每个整数都在[1,n]范围内，根据鸽巢原理至少有一个重复数字。要求：

不能修改原数组（不能排序或标记）
只能使用O(1)的额外空间
时间复杂度低于O(n²)

这实际上把暴力解法、排序法和哈希表法都排除了，必须寻找更聪明的办法。

4.2 Floyd判圈算法解析

这个问题可以转化为链表中的环检测问题，使用快慢指针（Floyd's Tortoise and Hare算法）：

将数组视为链表：nums[i]表示i指向的下一个节点
因为有重复数字，所以必然存在环
使用快指针（每次两步）和慢指针（每次一步）找到相遇点
然后从头开始，直到再次相遇即为重复数字

def findDuplicate(nums): slow = fast = nums[0] while True: slow = nums[slow] fast = nums[nums[fast]] if slow == fast: break slow = nums[0] while slow != fast: slow = nums[slow] fast = nums[fast] return slow