100、技巧-寻找重复的数

思路：

一个非常有效的解法是使用快慢指针法，这个方法灵感来自于寻找链表环的起点的算法。我们可以把数组中的元素看作是链表的指针，例如 nums[0] 指向 nums[nums[0]]。根据题目条件，数组中至少有一个数字重复，这会导致链表出现环。

解法步骤：

1. 找到环中的任意一个位置：

   • 使用快慢指针，快指针每次移动两步，慢指针每次移动一步。由于存在重复元素，这就像在有环的链表中找到相遇点。

2. 确定环的入口：

   • 当快慢指针首次相遇后，将其中一个指针（例如快指针）放回起始位置，然后两个指针都以相同的速度（每次一步）前进。当它们再次相遇时，该位置即为重复数字，也就是环的入口。

 代码如下：

public int findDuplicate(int[] nums) {
    int slow = nums[0];
    int fast = nums[nums[0]];
    
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[nums[fast]];
    }
    
    fast = 0; // 或 slow = 0，然后重新开始
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    
    return slow; // 或 fast，此时它们在环的入口处相遇
}