寻找重复数
把 nums[i] 看成 i 指向 nums[i] 的边，重复的数就是两条边汇入的节点——链表环的入口，Floyd 判环直接套用。
问题拆解
长度为 n + 1 的数组，元素都在 [1, n] 内，由抽屉原理必有重复，且题目保证重复的只有一个数（可能出现多次）。要求找出它——不能改数组，只许 O(1) 空间。
这两条限制把常规武器全缴了：排序要改数组，哈希表要 O(n) 空间。突破口在于换一种眼光看数组：把每个下标 i 看作一个节点，nums[i] 是它指向的下一个节点，即边 i → nums[i]。因为值域是 [1, n] 而下标能取到 0，没有边指回 0，从 0 出发的函数图必然走进一个环；而重复的数 d 被至少两个不同下标指向——两条边汇入同一个节点，d 正是环的入口。
数组一旦满足“值的范围落在下标范围内”，
i → nums[i]就构成一张函数图——找重复、找缺失这类题都可能借道链表的环技巧。
于是原题精确转化为链表题 142“环形链表 II”：找环入口，用 Floyd 快慢指针，只是把 node.next 换成 nums[i]。
Floyd 快慢指针找环入口
第一阶段快慢指针找相遇点：慢指针一次一步、快指针一次两步，都从 0 出发，必在环内相遇。第二阶段把一个指针放回起点，两指针同速前进，再次相遇处即环入口。原因是经典结论：设起点到入口距离 a、入口到相遇点距离 b，相遇时快指针路程是慢指针两倍，可推出从相遇点再走 a 步恰好回到入口——所以“一个从头、一个从相遇点”同步走 a 步，会师之处就是入口。
public int findDuplicate(int[] nums) {
int slow = nums[0], fast = nums[nums[0]]; // 各自先走一步、两步
while (slow != fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}
slow = 0; // 一个回到起点，同速前进
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow; // 再次相遇即环入口，也就是重复数
}
def findDuplicate(nums: List[int]) -> int:
slow, fast = nums[0], nums[nums[0]] # 各自先走一步、两步
while slow != fast:
slow = nums[slow]
fast = nums[nums[fast]]
slow = 0 # 一个回到起点，同速前进
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow # 再次相遇即环入口，也就是重复数
func findDuplicate(nums []int) int {
slow, fast := nums[0], nums[nums[0]] // 各自先走一步、两步
for slow != fast {
slow = nums[slow]
fast = nums[nums[fast]]
}
slow = 0 // 一个回到起点，同速前进
for slow != fast {
slow = nums[slow]
fast = nums[fast]
}
return slow // 再次相遇即环入口，也就是重复数
}
pub fn find_duplicate(nums: Vec<i32>) -> i32 {
let next = |i: usize| nums[i] as usize;
// 各自先走一步、两步
let (mut slow, mut fast) = (next(0), next(next(0)));
while slow != fast {
slow = next(slow);
fast = next(next(fast));
}
slow = 0; // 一个回到起点，同速前进
while slow != fast {
slow = next(slow);
fast = next(fast);
}
slow as i32
}
最容易错的是初始化：如果 slow 和 fast 都从 0 出发再进 while slow != fast 判断，循环体一次都不会执行。要么先各走一步和两步（如上），要么用 do-while 语义。另一个隐蔽点是值域保证了 nums[i] 永远是合法下标——0 不在值域里，所以不会有自环卡在起点，这条链一定通向环。
值域二分计数
不习惯图论视角，还有一条更“正统”的路：对值域（不是下标）二分。取 mid，数一数数组里小于等于 mid 的元素个数 cnt：若没有重复，cnt 应不超过 mid；cnt > mid 说明重复数被挤在 [1, mid] 里，否则在 [mid+1, n]。每轮扫一遍数组计数，区间折半。
public int findDuplicate(int[] nums) {
int lo = 1, hi = nums.length - 1; // 在值域 [1, n] 上二分
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int cnt = 0;
for (int num : nums) {
if (num <= mid) cnt++;
}
if (cnt > mid) {
hi = mid; // 抽屉溢出，重复数在左半段
} else {
lo = mid + 1;
}
}
return lo;
}
def findDuplicate(nums: List[int]) -> int:
lo, hi = 1, len(nums) - 1 # 在值域 [1, n] 上二分
while lo < hi:
mid = (lo + hi) // 2
cnt = sum(1 for num in nums if num <= mid)
if cnt > mid:
hi = mid # 抽屉溢出，重复数在左半段
else:
lo = mid + 1
return lo
func findDuplicate(nums []int) int {
lo, hi := 1, len(nums)-1 // 在值域 [1, n] 上二分
for lo < hi {
mid := (lo + hi) / 2
cnt := 0
for _, num := range nums {
if num <= mid {
cnt++
}
}
if cnt > mid {
hi = mid // 抽屉溢出，重复数在左半段
} else {
lo = mid + 1
}
}
return lo
}
pub fn find_duplicate(nums: Vec<i32>) -> i32 {
let (mut lo, mut hi) = (1i32, nums.len() as i32 - 1); // 在值域 [1, n] 上二分
while lo < hi {
let mid = lo + (hi - lo) / 2;
let cnt = nums.iter().filter(|&&num| num <= mid).count() as i32;
if cnt > mid {
hi = mid; // 抽屉溢出，重复数在左半段
} else {
lo = mid + 1;
}
}
lo
}
注意二分的对象是值域 [1, n]，数组本身无序也不需要有序——单调的是计数函数 cnt(x)，这类“答案二分”不依赖数组有序。代价是每轮都要全量扫描，时间 O(n log n)，比 Floyd 慢一个 log，但推理门槛低，想不起环技巧时是可靠的退路。
复杂度
| 指标 | 复杂度 | 原因 |
|---|---|---|
| 时间（Floyd） | O(n) |
两个阶段各至多绕环常数圈 |
| 时间（二分） | O(n log n) |
log n 轮，每轮全量计数 |
| 空间 | O(1) |
两种解法都只用几个变量 |
可以迁移的模式
- 值域
[1, n]、下标[0, n]的数组，试着把i → nums[i]画成图，重复与环、缺失与断链常常对应； - Floyd 判环的两段式（找相遇点 → 找入口）值得背下来，142 和本题共用一套推导；
- “答案二分”不要求数据有序，只要求某个判定函数随答案单调——计数就是最常见的判定。
限制越苛刻（只读、O(1) 空间），越说明出题人埋了一个结构性观察，先找结构再找算法。