寻找重复数 图解题解
数组里藏着一个重复数，不改数组不用哈希——把它转换成链表找环问题。
寻找重复数，把数组当链表来跑：下标 i 对应节点 i，nums[i] 就是它的「next 指针」。重复数字意味着两个下标都指向同一个节点，必然构成一个环，而重复数就是环的入口。之后用快慢指针找到相遇点，再让一个指针回到起点 0、两者同步走，再次相遇处就是环入口，也就是那个重复数。
这道题到底在问什么
- 输入
- nums = [1,3,4,2,2]
- 输出
- 2
- 输入
- nums = [3,1,3,4,2]
- 输出
- 3
- 输入
- nums = [3,3,3,3,3]
- 输出
- 3
最优解：一步一步想明白
- 3这题的限制条件是解法选择的核心。
- 4这和链表环 II 是同一个模型，只是 next 指针藏在数组值里。
- 5nums = [1,3,4,2,2]从下标 0 出发：0 指向 1，1 指向 3，3 指向 2，2 指向 4，4 又指回 2。重复数字 2 不是凭空出现的，它是这个环的入口。
- 6slow = nums[0]; fast = nums[0]代码从 nums[0] 开始，而不是从下标 0 开始；之后每一步都按 nums[当前节点] 往前走。
- 7fast 第 1 跳 = nums[1] = 3fast 一轮要走两步，先看它的第一跳：从 1 沿 nums[1] 走到 3。
- 8slow=nums[1]=3; fast=nums[nums[1]]=2slow 这轮只走一步停在 3；fast 接着第二跳从 3 走到 2。一轮过后 slow=3、fast=2。
- 9slow=nums[3]=2; fast=nums[nums[2]]=2第一次相遇证明路径进入了环，但这个相遇点只是环内某点，还要继续找环入口。
- 10slow = nums[0]Floyd 第二阶段：slow 回到起点，fast 留在相遇点，两个指针之后都每次走一步。
- 11slow=nums[1]; fast=nums[2]两条路径到环入口的距离会同步抵消，所以只需要同速前进。
- 12slow=nums[3]; fast=nums[4]第二次相遇的位置就是环入口。这里入口节点是 2，所以重复数字是 2。
- 13return slow下标 3 和下标 4 这两个不同位置都填了 2，于是两条边一起指向节点 2，这就是“重复”在函数图里长出环的样子。
- 15这题真正要学的是“数组函数图”建模：看到值域恰好能做下标，就该想到连边找环。
⚠️ 容易写错的地方
✗ 错：相遇即 return，把第一次 meet 当答案
✓ 对：相遇后把 slow 拨回起点，再同速走到入口
第一次相遇点只是环内某点，不一定是入口；入口才等于重复数。
✗ 错：第一阶段 fast 也只走一步
✓ 对：第一阶段 fast 必须 nums[nums[fast]] 走两步
两指针同速永远不会相遇；只有快指针二倍速才能在环内追上慢指针。
✗ 错：两个 while 用同样的循环条件
✓ 对：第一阶段先走后判(do-while)，第二阶段先判后走
起点 slow==fast，若第一阶段先判会立刻误判相遇直接退出。
完整代码（Python / C++ / Java）
Python
class Solution:
def findDuplicate(self, nums):
slow = nums[0]
fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slowC++
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = nums[0], 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;
}
};Java
class Solution {
public int findDuplicate(int[] nums) {
int slow = nums[0], 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;
}
}套路模板：Floyd 找环入口（可背骨架）
# 通用骨架：把题转成 next(x) 后照填三步
def floyd_entry(start, nxt):
# 阶段1：先走后判，找环内相遇点
slow = fast = start
while True:
slow = nxt(slow) # 慢: 1 步
fast = nxt(nxt(fast)) # 快: 2 步
if slow == fast: break
# 阶段2：slow 回起点，两者同速找入口
slow = start
while slow != fast:
slow = nxt(slow); fast = nxt(fast)
return slow # 入口
# 287 套用：next(x)=nums[x], start=nums[0]// 骨架：定义 next(x) 后填三步
// 阶段1 先走后判 (do-while)
int slow = start, fast = start;
do {
slow = nextOf(slow); // 慢 1 步
fast = nextOf(nextOf(fast)); // 快 2 步
} while (slow != fast);
// 阶段2 回起点, 同速走到入口
slow = start;
while (slow != fast) {
slow = nextOf(slow);
fast = nextOf(fast);
}
return slow; // 入口
// 287: nextOf(x)=nums[x], start=nums[0]// 骨架：定义 next(x) 后填三步
// 阶段1 先走后判 (do-while)
int slow = start, fast = start;
do {
slow = nextOf(slow); // 慢 1 步
fast = nextOf(nextOf(fast)); // 快 2 步
} while (slow != fast);
// 阶段2 回起点, 同速走到入口
slow = start;
while (slow != fast) {
slow = nextOf(slow);
fast = nextOf(fast);
}
return slow; // 入口
// 287: nextOf(x)=nums[x], start=nums[0]复杂度
时间复杂度
O(n)
第一阶段相遇、第二阶段找入口都在线性步数内完成，合起来仍是 O(n)。
空间复杂度
O(1)
全程只新增 slow、fast 两个整数变量，不开数组也不开集合。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 寻找重复数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么第一阶段 fast 要走两步、slow 走一步？+
二者速度差为 1，每轮把环内间距缩小 1，所以一定能在环内追上相遇；若同速则永远差着固定距离碰不到。
第二阶段为什么“拨回起点再同速走”就能停在入口？+
设头到入口距 a、入口绕环再回相遇点距 b。第一次相遇时可推出 a 与“相遇点继续走到入口”的距离相等，所以两指针同速走 a 步会同时到入口。
如果题目不保证恰好一个重复数，这个解法还成立吗？+
不成立。本解的前提是“函数图里有且只有一个环、且重复值就是唯一入口”；若有多个重复或不保证有重复，需改用计数或值域二分。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。