题目

解法：快慢指针

思路

将数组视为链表，利用 Floyd 判圈算法（龟兔赛跑）寻找环入口。数组索引作为节点，值作为指向下一节点的指针，由于必存在重复，因此会形成环，环入口即为重复数字。

该方法正确性基于鸽巢原理：n+1 个元素映射到 n 个取值范围必然产生环。设起点到环入口距离为 a，相遇点到入口距离为 b，环长为 L。快指针速度是慢指针两倍，相遇时满足 a + b = nL。重置一指针至起点后，两指针同步移动，当各走 a 步时必在环入口相遇，此时即为重复值。

• Step 1: 初始化 slow 和 fast 为 nums[0]
• Step 2: 执行 do-while 循环，slow 走一步，fast 走两步，直到相遇
• Step 3: 初始化 ptr 为 nums[0]
• Step 4: ptr 和 slow 每次各走一步，直到相遇
• Step 5: 返回相遇点值即为重复数

复杂度

• 时间复杂度: $O(n)$
• 空间复杂度: $O(1)$

代码

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[0];
        do{
            slow = nums[slow];
            fast = nums[nums[fast]];
        }while(slow != fast);

        int ptr = nums[0];

        while(ptr != slow){
            ptr = nums[ptr];
            slow = nums[slow];
        }

        return ptr;
    }
};