好的，我们来看 LeetCode 第 287 题：“寻找重复数”。这是一个非常经典且巧妙的问题，适合用来深入理解数组操作、二分查找和快慢指针法。
1. 题目描述
题干：
给定一个包含 n + 1 个整数的数组 nums，其数字都在 [1, n] 范围内（包括 1 和 n）。
假设 nums 中有且只有一个重复的整数，找出这个重复的数。
要求：
- 不能修改数组（假设数组是只读的）。
- 只能使用额外的 O(1) 空间。
- 时间复杂度小于 O(n²)。
示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
2. 初步分析
题目给了关键限制：
- 数组长度 = n + 1，元素取值范围 [1, n]。
- 根据抽屉原理（鸽笼原理），n+1 个苹果放进 n 个抽屉，至少有一个抽屉有至少两个苹果 → 一定存在重复数字。
- 只有一个数字重复，但可能重复多次（不止两次）。
3. 常见思路与排除
3.1 排序法（违反限制）
排序后重复数会相邻，扫描一遍即可。
但排序会修改数组，且需要 O(n log n) 时间，O(n) 或 O(log n) 额外空间（取决于排序算法），不满足 O(1) 空间要求。
3.2 哈希表法（违反限制）
遍历数组，用哈希表记录出现过的数字，遇到已存在的就是重复数。
时间 O(n)，但空间 O(n)，不满足 O(1) 空间要求。
3.3 暴力双重循环（时间复杂度高）
对每个元素，检查后面是否有相同元素。
时间 O(n²)，不满足“小于 O(n²)”的要求。
4. 解法一：二分查找法（不修改数组，O(1) 空间，O(n log n) 时间）
4.1 思路
虽然数组无序，但数字范围是 [1, n]，我们可以二分查找重复的数值，而不是二分索引。
核心思想：
对于中间数 mid = (1 + n) / 2，统计原数组中 ≤ mid 的元素个数 count：
- 如果 count > mid，说明重复数字在左半区间 [1, mid]（因为如果无重复，≤ mid 的数字个数应该恰好等于 mid）。
- 否则重复数字在右半区间 [mid+1, n]。
为什么？
举例：n=5，数组长度 6，数字范围 [1,5]。
如果没有重复，≤ mid 的数字个数 = mid。
如果重复数 ≤ mid，那么 ≤ mid 的数字个数至少为 mid + 1（多了一个重复的）。
4.2 步骤
- 初始化 left = 1, right = n。
- while left < right:
- mid = (left + right) / 2
- 遍历数组，统计有多少个元素 ≤ mid，记为 count。
- 如果 count > mid，重复数在 [left, mid]，令 right = mid。
- 否则重复数在 [mid+1, right]，令 left = mid + 1。
- 返回 left。
4.3 示例
nums = [1,3,4,2,2], n=4
初始 left=1, right=4
- 迭代 1: mid=2，统计 ≤2 的元素：1,2,2 → count=3 > 2 → right=2
- 迭代 2: left=1, right=2, mid=1，统计 ≤1 的元素：1 → count=1 ≤1 → left=2
- left=2, right=2 结束，输出 2。
时间复杂度：O(n log n)（二分 log n 次，每次遍历 n 个元素）
空间复杂度：O(1)
5. 解法二：快慢指针法（Floyd 判圈算法，O(n) 时间，O(1) 空间）
5.1 将数组视为链表
这是一个非常巧妙的技巧：
把数组下标 0 到 n 看作节点，数组元素值 nums[i] 表示节点 i 指向的下一个节点下标。
例如 nums[0] = 1 表示 0 → 1，nums[1] = 3 表示 1 → 3，等等。
因为数字范围 [1, n]，而数组长度 n+1，所以每个节点 i 的出度都是 1，且指向的节点在 [1, n] 范围内（除了节点 0 的入度可能为 0，但其他节点入度至少为 1）。
由于有重复数字，必然存在两个不同节点指向同一个节点，因此链表中存在环，且环的入口就是重复数字。
为什么？
- 重复数字 = 有多个节点指向它 → 该节点入度 >1 → 环的入口。
5.2 算法步骤（Floyd 判圈找环入口）
- 慢指针 slow = nums[0]，快指针 fast = nums[nums[0]]。
- 第一阶段：找相遇点
while slow != fast:
slow = nums[slow]
fast = nums[nums[fast]] - 第二阶段：找环入口
fast = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast] - 返回 slow（即重复数）。
5.3 示例
nums = [1,3,4,2,2], n=4
- 索引：0,1,2,3,4
- 值：1,3,4,2,2
- 链表：0→1→3→2→4→2（形成环 2→4→2）
第一阶段：
- slow = nums[0] = 1, fast = nums[nums[0]] = nums[1] = 3
- slow: 1→3→2, fast: 3→2→4→2→4（快慢相遇在 2？我们一步步来）
详细：
- slow=1, fast=3
- slow=nums[1]=3, fast=nums[nums[3]]=nums[2]=4
- slow=nums[3]=2, fast=nums[nums[4]]=nums[2]=4
- slow=nums[2]=4, fast=nums[nums[4]]=nums[2]=4
相遇在 4。
第二阶段：
- fast 重置为 0
- slow=4, fast=0
- slow=nums[4]=2, fast=nums[0]=1
- slow=nums[2]=4, fast=nums[1]=3
- slow=nums[4]=2, fast=nums[3]=2
相遇在 2 → 重复数是 2。
时间复杂度：O(n)
空间复杂度：O(1)
6. 总结
| 方法 | 时间复杂度 | 空间复杂度 | 是否修改数组 | 核心思想 |
|---|---|---|---|---|
| 二分查找 | O(n log n) | O(1) | 否 | 利用数值范围二分，统计个数 |
| 快慢指针 | O(n) | O(1) | 否 | 将数组视为链表，找环入口 |
推荐掌握快慢指针法，因为它是最优解，且能锻炼将问题转化为链表环检测的抽象能力。
这道题的关键在于理解数组下标与值的映射关系，从而将“找重复数”转化为“链表找环”的问题。
如果你对哪一部分还有疑问，我可以进一步解释。