链接：https://leetcode.cn/problems/find-the-duplicate-number/description/?envType=study-plan-v2&envId=top-100-liked
思路
将数组 nums 映射为链表，nums[i] 表示 i 节点指向 nums[i] 节点，由于 nums[i] 的取值范围为 [1,n]，所以整个数组形成的链表必然存在环，这时可以使用快慢指针检测环并找到环的入口。
具体步骤
- 使用快慢指针，当第一次相遇时，令慢指针从头开始移动，快指针照常移动。
- 当快慢指针再次相遇，此时的节点就是环的入口，即其索引就是重复的数。
证明
如图所示，假设 ：
a：起点到环入口的距离b：环入口到第一次相遇的距离c：环的长度m：第一次相遇时快指针在环里转的圈数
那么第一次相遇时有：
\[\begin{align*}
s_{1} &= a + b \quad \text{（慢指针走的步数）} \\
s_{2} &= 2s = a + b + cm \quad \text{（快指针走的步数）}
\end{align*}
\]
联立可得
\[a = cm - b = c(m-1) + (c - b)
\]
所以当第二次相遇时，快慢指针都恰好走到环的入口。
复杂度分析
时间复杂度
\(O(n)\)
- 第一阶段：快慢指针寻找相遇点，最坏情况需要遍历 \(O(n)\) 步。
- 第二阶段：重置指针后寻找环入口，最坏情况需要 \(O(n)\) 步。
- 总时间：\(O(n) + O(n) = O(n)\)。
空间复杂度
\(O(1)\)
只使用了 slow、fast 两个整型变量，没有使用额外数据结构。
代码
class Solution {
public:int findDuplicate(vector<int>& nums) {int n = nums.size();int slow = 0, fast = 0;do {slow = nums[slow];fast = nums[nums[fast]];} while (slow != fast);slow = 0;while (slow != fast) {slow = nums[slow];fast = nums[fast];}return slow;}
};