LeetCode287.找到重复数

更新: 6/9/2026 字数: 0 字 时长: 0 分钟

题目链接：287. 寻找重复数

题目大意很好理解，我们只需要从n+1个整数数组中找出唯一一个重复的数字（数字都在[1,n]内），要求不修改 数组 nums 且只用常量级 O(1) 的额外空间。

既然数字都在[1,n]内，那么我们可以对n -> f[n]建立映射关系，比如[1,3,4,2,2]:

0 -> 1

1 -> 3

3 -> 2

2 -> 4

4 -> 2

我们从下标0出发，以f[i]作为新的下标这样去查找，我们可以产生一个类似于链表的序列，然后我们不难发现，这个链表实际上是一个环。

因为如果有重复的数，那么这个链表必然会产生一个多对一的映射，就一定会产生环。那么就转换成了142. 环形链表 II这个题，采用快慢指针的方式，快慢指针的证明方式可以参考题解。

那么这里是数组的形式，如何实现快慢指针呢？我们可以通过链表的走一步和走两步推断出这里的快慢指针走法：

slow = nums[slow];
fast = nums[nums[fast]];

这样就完成了快慢指针。参考代码如下：

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0;
        slow = nums[slow];
        fast = nums[nums[fast]];
      // 快慢指针，找到相遇点
        while(slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
      // 一个在头，一个在相遇点，最后一定会在环的入口相遇
        int tmp = 0;
        while(tmp != slow) {
            tmp = nums[tmp];
            slow = nums[slow];
        }
        return tmp;
    }
};