寻找重复数
Find the Duplicate Number
n + 1 个数都在 1..n 之间，只有一个数重复；不修改数组、只用 O(1) 空间找出它。
在力扣中练习题目描述
给定一个包含 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 <= 105nums.length == n + 11 <= nums[i] <= nnums中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
进阶：
- 如何证明
nums中至少存在一个重复的数字? - 你可以设计一个线性级时间复杂度
O(n)的解决方案吗？
解题思路
Floyd 判圈 · 数组当链表
i → nums[i] 就是一条有环链表，环的入口就是重复的数
排序会改变数组，额外集合又超出常数空间。利用值都在 1..n：把下标 i 指向 nums[i]，就得到一张每个节点只有一个后继的引用图。从 0 出发最终会进入一个环。
自拟主例 [2,5,4,6,3,1,4] 的路径是 0→2→4→3→6→4，重复数为 4。图中大字是下标，下方小字是数组值，两个概念不能混淆。
slow 走一步到 3，fast 走两步到 3，在环内相遇。
第一阶段 slow 走一步、fast 走两步，保证在环内相遇；这个相遇点还不一定是入口。第二阶段把 slow 放回 0，两者各走一步，再次相遇才得到入口。
入口 4 有两个不同来源指向它，对应数组里出现两次的 4。图中另一条环不可从 0 到达，不影响这条路径；代码全程只读取 nums，不修改数组。
易错点
- 第二阶段忘了把 slow 放回 0：两人已经相等，第二次循环直接跳过，返回的是相遇点而不是入口。
- 第一阶段里 fast 只走一步，快慢指针同速，永远追不上。
- 以为相遇点就是答案：相遇点在环里，入口才是重复的数。
二分答案 · 数个数
对值域二分：若 ≤ mid 的数超过 mid 个，重复数就在左半边
正确且不修改数组，额外空间 O(1)，但比 Floyd 多出一层二分，时间为 O(n log n)。
另一种完全不碰指针的做法：二分答案。
重复数 x 有一个单调性质：对任意 mid，统计数组里 ≤ mid 的个数 cnt。
cnt > mid：1..mid 里塞了超过 mid 个数，必然有重复，答案在[1, mid]；- 否则答案在
[mid+1, n]。
原因是 1..mid 一共只有 mid 个不同的整数，落下超过 mid 个元素就一定有重复。反过来，cnt ≤ mid 时，大于 mid 的元素至少有 (n+1)−mid 个，而右边只有 n−mid 个位置，重复只能出在右半边。
于是对值域 [1, n] 二分，每轮 O(n) 数一遍，总复杂度 O(n log n)，空间 O(1)。
它比 Floyd 慢一个 log，但思路更接近「二分答案」的通用套路，也不依赖「值恰好能当下标」这种巧合。
- 1答案区间取 [1, n]，n = nums.size() - 1。
- 2取 mid，遍历数组统计 ≤ mid 的个数 cnt。
- 3cnt > mid 则答案在左半 [lo, mid]，否则在右半 [mid+1, hi]。
- 4区间缩到单点时，lo 就是重复数。
易错点
- 把 cnt > mid 写成 cnt >= mid，值域收缩方向反了，答案会偏移。
- hi 取成 nums.size()，值域多了一段永远不可能有重复的区间。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
nums = [2,5,4,6,3,1,4]把 i → nums[i] 当作 next：slow=2，fast=4。图中大字是下标。
查看 C++ 代码
延伸阅读
- Floyd 判圈是链表找环的通用工具：环形链表（141）判有没有环，环形链表 II（142）找入口，本题只是把 next 指针换成了 nums[i]。
- 「值域 1..n + 长度 n+1」这个条件非常强，几乎所有 O(1) 空间解法都建立在它上面；少了它就只能排序或哈希。
- 二分解法可以推广到「找第 k 小的缺失/重复元素」这类题，因为它只依赖计数，不依赖数组有序。