287. 寻找重复数

287. 寻找重复数

中等

给定一个包含 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

提示：

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

📝 核心笔记：寻找重复数 (Find the Duplicate Number)

1. 核心思想 (一句话总结)

“抽象链表：把数组下标看作‘当前节点’，数组的值看作‘Next 指针’。因为有重复数字（多个下标指向同一个值），所以这个链表里一定有一个环，那个环的入口就是重复的数。”

• 映射关系：index node，nums[index] next node。
• 为何成环：因为值在 [1, n] 之间，而下标覆盖 0 到 n。如果有两个下标 i 和 j 的值都是 x，说明有两个节点指向了同一个节点 x，这在链表中就形成了环的入口。
• 起点选择：题目限定值在 1 到 n，所以下标 0 一定不在环内（没有人的值是 0，没人指向 0），它最适合做链表的头节点。

2. 算法流程 (Floyd's Cycle Detection)

• • 定义 slow 和 fast 指针，都从 0 开始。
  • slow 走一步：slow = nums[slow]。
  • fast 走两步：fast = nums[nums[fast]]。
  • 当 slow == fast 时，说明在环内相遇了，跳出循环。

• • 保持 slow 在相遇点不动。
  • 新建一个指针 head 重置回起点 0。
  • slow 和 head 同时每次走一步。
  • 当它们再次相遇时，相遇点就是环的入口（即重复的数字）。

🔍 代码回忆清单

// 题目：LC 287. Find the Duplicate Number
class Solution {
public int findDuplicate(int[] nums) {
// 1. 初始化快慢指针
// 从下标 0 开始，因为 0 不在数值范围 [1, n] 内，一定是"链表头"
int slow = 0;
int fast = 0;

// 2. 第一阶段：找环内相遇点
while (true) {
slow = nums[slow]; // 相当于 slow.next
fast = nums[nums[fast]]; // 相当于 fast.next.next

if (fast == slow) { // 追上了！
break;
}
}

// 3. 第二阶段：找环入口 (重复数)
// 一个指针从起点出发，一个指针从相遇点出发
int head = 0;
while (slow != head) {
slow = nums[slow]; // 步速调整为 1
head = nums[head]; // 步速也是 1
}

// 4. 相遇的地方就是入口
return slow;
}
}

⚡ 快速复习 CheckList (易错点)

• [ ] 为什么快指针不会越界？

• • 因为题目保证所有数字都在 [1, n] 之间，且数组长度是 n+1。
  • nums[x] 永远是一个合法的下标。这也是为什么这道题能转成链表的关键前提。

• [ ] 为什么不能直接用 Set？

• • 用 Set 空间复杂度是 。题目进阶要求 $O(1)$ 空间。
  • 如果是面试，用 Set 能做出来，但拿不到满分。

• [ ] 为什么 slow 和 head 每次一步一定会相遇？

• • 这是一个数学证明）。
  • 简单记结论：“相遇点到入口的距离” 等于 “起点到入口的距离”。

🖼️ 数字演练

nums = [1, 3, 4, 2, 2]

映射图：0->1, 1->3, 3->2, 2->4, 4->2。

(环是 2->4->2… 入口是 2)

• • Start: S=0, F=0.
  • Step 1: S=nums[0]=1, F=nums[nums[0]]=3.
  • Step 2: S=nums[1]=3, F=nums[nums[3]]=nums[2]=4.
  • Step 3: S=nums[3]=2, F=nums[nums[4]]=nums[2]=4.
  • Step 4: S=nums[2]=4, F=nums[nums[4]]=nums[2]=4.
  • 相遇: S=4, F=4. (注意：相遇点不一定是 2，这里是在环里的 4 相遇)。

• • Head 重置为 0, Slow 保持为 4.
  • Step 1: Head=nums[0]=1, Slow=nums[4]=2.
  • Step 2: Head=nums[1]=3, Slow=nums[2]=4.
  • Step 3: Head=nums[3]=2, Slow=nums[4]=2.
  • 相遇: Head=2, Slow=2.