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

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

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

示例 1：

输入：nums = [1,3,4,2,2]
输出：2

示例 2：

输入：nums = [3,1,3,4,2]
输出：3

示例 3 :

输入：nums = [3,3,3,3,3]
输出：3

解题思路

Floyd 判圈算法（快慢指针法），把数组当链表

• 将索引 i 视为节点
• 将 nums[i] 视为节点 i 指向的下一个节点的索引

因为存在重复的数字，意味着有两个不同的索引指向了同一个值（即同一个“下一个节点”），这在链表结构中就形成了一个环。那个重复的数字，就是环的入口。

第一阶段：寻找相遇点：

• 定义两个指针：slow（慢指针）和 fast（快指针）
• 初始时，slow = nums[0], fast = nums[nums[0]]。
• 慢指针每次走一步（slow = nums[slow]）。
• 快指针每次走两步（fast = nums[nums[fast]]）。
• 由于存在环，快慢指针最终一定会在环内相遇。

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

• 当 slow 和 fast 相遇后，保持 slow 在相遇点不动。
• 新建一个指针 finder（或者重置 fast）指向起点 0。
• 让 slow 和 finder 每次都各走一步。
• 当它们再次相遇时，相遇的节点值就是环的入口，即我们要找的重复整数。

注意快慢指针时，一定要让 fast 和 slow 先动一步，即用 do-while

Java实现

    public int findDuplicate(int[] nums) {
        int fast = 0;
        int slow = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }  while (slow != fast);
        int find = 0;
        while (find != slow){
            find = nums[find];
            slow = nums[slow];
        }
        return find;
    }