LeetCode 287：快慢指针巧解重复数

LeetCode287

给定一个包含n + 1个整数的数组nums，其数字都在[1, n]范围内（包括1和n），可知至少存在一个重复的整数。

假设nums只有一个重复的整数，返回这个重复的数。

你设计的解决方案必须不修改数组nums且只用常量级O(1)的额外空间。

示例 1：

输入：nums = [1,3,4,2,2]，输出：2

示例 2：

输入：nums = [3,1,3,4,2]，输出：3

示例 3 :

输入：nums = [3,3,3,3,3]，输出：3

Python解法

1.二分查找

class Solution: def findDuplicate(self, nums: List[int]) -> int: left = 1 right = len(nums) - 1 while left < right: mid = (left + right) // 2 cnt = 0 for num in nums: if num <= mid: cnt += 1 if cnt > mid: right = mid else: left = mid + 1 return left

2.快慢指针

class Solution: def findDuplicate(self, nums: List[int]) -> int: slow = fast = 0 # 第一阶段：快慢指针不同速，环内相遇 while True: slow = nums[slow] fast = nums[nums[fast]] if slow == fast: break # 第二阶段：slow重置起点，同速找环入口 slow = 0 while slow != fast: slow = nums[slow] fast = nums[fast] return slow

Java解法

1.二分查找

class Solution { public int findDuplicate(int[] nums) { int left = 1; int right = nums.length - 1; int mid = 0; int cnt = 0; while(left < right){ mid = (left + right) / 2; cnt = 0; for(int num : nums){ if(num <= mid){ cnt++; } } if(cnt > mid){ right = mid; }else{ left = mid + 1; } } return left; } }

2.快慢指针

public int findDuplicate(int[] nums) { int slow = 0, fast = 0; // 1.快慢指针不同速，直到环内相遇 do { slow = nums[slow]; // 走1步 fast = nums[nums[fast]]; // 走2步 } while (slow != fast); // 2.慢指针放回起点，二者同速前进 slow = 0; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; }

C++解法

1.二分查找

class Solution { public: int findDuplicate(vector<int>& nums) { int left = 1; int right = nums.size() - 1; int mid = 0; int cnt = 0; while(left < right){ mid = (left + right) / 2; cnt = 0; for(int num : nums){ if(num <= mid){ cnt++; } } if(cnt > mid){ right = mid; }else{ left = mid + 1; } } return left; } };

2.快慢指针

#include <vector> using namespace std; class Solution { public: int findDuplicate(vector<int>& nums) { int slow = 0, fast = 0; // 第一步：快慢指针相遇 do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast); // 第二步：同速前进找入口 slow = 0; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; } };

快慢指针

快慢指针核心优势：仅 O (1) 额外空间，一次 / 两次遍历完成，无需额外容器，分为「快慢步速差指针」「前后同步快慢指针」两大类。

场景 1：链表判环、找环入口（Floyd 龟兔算法）

适用题目

• LeetCode141 环形链表（判断链表是否存在环）
• LeetCode142 环形链表 II（找到环的起始节点）
• LeetCode287 寻找重复数（数组映射为带环链表）

思路：快指针一次走 2 步，慢指针一次 1 步，有环必相遇；再同速找入口。

场景 2：链表 / 数组找中点、倒数第 k 个节点

1）找链表中点（LeetCode876 链表的中间结点）

slow 走 1 步，fast 走 2 步；fast 走到末尾时，slow 刚好在中点。

2）倒数第 k 个节点（LeetCode19 删除链表倒数第 N 个结点）

快指针先提前走 k 步，再快慢同速向后走；fast 到末尾时 slow 指向倒数第 k 个。

场景 3：原地数组分区、移动元素（如 LeetCode283 移动零）

slow 记录下一个合法元素存放位置，fast 遍历数组；fast 找到符合条件元素时，和 slow 交换 / 覆盖，slow 前进。 类似题目：移除元素、颜色分类。

场景 4：链表判回文（LeetCode234）

快慢指针找到链表中点，反转后半段，再前后指针同步比对。

场景 5：链表奇偶重排、拆分链表

用快慢指针分割链表为前后两部分，再重组。

场景 6：滑动窗口类优化（快慢指针 / 滑动窗口双指针）

slow 为窗口左边界，fast 为右边界，满足条件收缩左边界；常用于子数组求和、最长无重复子串等。

局限

1. 仅适用于线性结构（链表、可映射为链表的数组）；
2. 环形问题需要数学推导理解，逻辑门槛高于二分、哈希；
3. 无法处理多环、多入口复杂结构（仅单环单入口场景）。