当前位置：首页 > news >正文

LeetCode 287. 寻找重复数：从直觉到 Floyd 判圈的完整推导

news 2026/6/29 17:00:10

一、题目描述

给定一个长度为n + 1的数组nums，其中：

所有数字都在[1, n]范围内
只有一个重复的数字（但可能重复多次）

请找出这个重复的数字。

⚠️限制条件（重点）：

❌ 不能修改原数组
✅ 只使用O(1) 额外空间

示例：

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

二、为什么这题“看起来简单但很难”

如果你允许修改数组，这题很简单：

方法	思路	问题
排序	相邻比较	修改数组 ❌
HashSet	记录出现次数	额外空间 ❌

但题目明确要求：

不能改数组 + O(1) 空间

👉 于是我们必须把“数组本身”当成某种结构来推理。

三、核心洞察：把数组看成「链表」

1️⃣ 关键抽象

数组下标：0 ~ n

数组取值：1 ~ n

我们可以把数组理解成一个映射函数：

f(i) = nums[i]

从任意位置i出发，不断执行：

i → nums[i] → nums[nums[i]] → ...

👉 这本质上是一条链表路径

2️⃣ 为什么一定有环？

节点数：n + 1
值域：1 ~ n（没有 0）

➡️必然存在某个节点被指向多次

➡️必然形成环

而：

环的入口，就是那个重复的数字

四、Floyd 判圈算法（快慢指针）

这正是Linked List Cycle II 的翻版。

Step 1：找相遇点（快慢指针）

slow = nums[slow] fast = nums[nums[fast]]

最终它们一定在环内某点相遇。

Step 2：找环的入口（重复数）

将其中一个指针重置到起点：

slow = 0

然后同步前进：

slow = nums[slow] fast = nums[fast]

再次相遇的位置，就是重复的数字。

五、结合例子理解（非常关键）

以nums = [1,3,4,2,2]为例：

索引路径：

0 → 1 → 3 → 2 → 4 → 2 → 4 → ...

结构如下：

0 → 1 → 3 → 2 ↓ 4

环：2 → 4 → 2
环的入口：2
✅ 答案就是2

六、为什么这个方法一定正确？

阶段	目的
快慢指针相遇	证明存在环
重置一个指针	对齐起点与环入口距离
同步移动	数学上必然在入口相遇

这是一个严格可证明 的算法，不是“玄学”。

七、Java 实现（面试标准版）

class Solution { public int findDuplicate(int[] nums) { int slow = 0, fast = 0; // Step 1: 找到相遇点 do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast); // Step 2: 找到环的入口（重复数） slow = 0; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; } }