287. 寻找重复数（Find the Duplicate Number）
频次 ★★★★ · 难度 🟡 · 高频：字节/腾讯
题目
n+1 个整数存入长度为 n+1 的数组，数字范围 [1, n]，只有一个数字重复（至少出现两次），其余每个出现恰好一次。不修改数组，O(1) 空间，找出重复的那个数。
示例：
输入: nums = [1,3,4,2,2]
输出: 2
输入: nums = [3,1,3,4,2]
输出: 3
思路
Floyd 判圈（快慢指针映射到下标）：把数组的下标当成节点，nums[i] 作为 next 指针——从 i 出发下一步到 nums[i]。因为有重复数字，这个「下标→值」映射必然成环，环入口就是重复值。
将 nums[0] 作为起点，快慢指针同 141/142 的链表判环逻辑：slow 走一步（slow = nums[slow]），fast 走两步（fast = nums[nums[fast]]），相遇后从头出发与 slow 同步前进，相遇点即环入口（重复数）。
代码
public int findDuplicate(int[] nums) {
int slow = nums[0];
int fast = nums[0];
// 第一阶段：找到环内相遇点
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
// 第二阶段：找环入口（重复数）
slow = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}复杂度
- 时间：O(n) —— 每个指针最多走 n 步
- 空间：O(1)
边界条件
- n = 1 时，数组
[1,1]，slow=nums[0]=1，fast=nums[0]=1，do-while 直接满足条件，第二阶段 slow=nums[0]=1 不动，返回 1 正确 - 重复数出现超过两次（如
[2,2,2,2]）：映射仍会成环，环入口仍是重复值
变式
- 数组允许修改（排序或下标归位）：直接排序找相邻相等，或把每个数放到「值-1」的下标上，第一个冲突的就是重复数。本题限制不修改数组
- 求重复数具体出现次数：本题只需找出值，不需统计次数。如果需要频次，用哈希表或二分值域（剑指 Offer 的计数法），后者 O(n log n) 但满足 O(1) 空间
易错点
- 第一阶段用 do-while 而非 while：必须让 slow 和 fast 先走一步再比较，否则初始相等直接退出
- 把数组当链表时「下标 i 指向 nums[i]」是有向边，节点数是数组长度 n+1，每个节点值域 [1,n] 保证不会越界
- 本题禁止修改数组（否则可以用原地哈希），也不能用额外哈希集（O(n) 空间不合格）
面试追问
- 为什么一定有环？ 鸽巢原理：n+1 个位置，值域只有 n 个不同值（[1,n]），最少有一个值出现两次，映射到下标就形成”两个不同的下标指向同一个值”，构成入环点
- 能不能用二分法（值域二分）？ 可以，统计 ≤mid 的元素个数，如果 count > mid 则重复数在 [1,mid] 范围内，否则在 (mid,n]。时间 O(n log n)，空间 O(1)，面试时作为另一种 O(1) 空间解法提到即可
- 如果允许修改数组，最好的解法是什么？ 原地归位：遍历时把 nums[i] 放到 nums[nums[i]-1] 位置，如果发现目标位置已经有相同的值，即找到重复数。时间 O(n)，空间 O(1)
关联题
- 基础：141. 环形链表 I、142. 环形链表 II —— Floyd 判圈的链表版本，完全相同的思路，只是把 next 指针替换成了 nums[i]
- 同套路：41. 缺失的第一个正数 —— 相同「下标即哈希」思想，但那题是改数组做原地置换
- 知识点：Floyd 判圈法本质是将「重复值」转化为「环入口」，见数组与字符串、链表