287 寻找重复数

一、题目

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

二、题解

整个过程分为两个阶段：

第一阶段：判断是否有环（找到相遇点）

1. 设置两个指针：慢指针 slow 每次走一步（slow = nums[slow]），快指针 fast 每次走两步（fast = nums[nums[fast]]）。

2. 因为有环，快指针一定会在环内某个位置“追上”慢指针。当它们相遇时，第一阶段结束。

第二阶段：寻找环的入口（即重复数）

1. 这是一个数学规律：当快慢指针相遇后，如果把其中一个指针（比如慢指针）重新放回起点（下标 0）。

2. 然后让两个指针每次都只走一步。

3. 当它们再次相遇时，相遇的位置，绝对就是环的入口，也就是我们要找的重复数字！

class Solution {
    public int findDuplicate(int[] nums) {
        // 第一阶段：快慢指针找相遇点
        // 初始化：慢指针走一步，快指针走两步
        int slow = nums[0];
        int 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;
    }
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$