https://leetcode.cn/problems/find-the-duplicate-number/description/

快慢指针

题意：寻找环口，环口元素是重复数。

简化理解：如果有环，则可以相遇。

• 如何相遇：step=1和 step=2 一定在环内相遇
• 相遇后：length（step=1重新从开始走到环口）= length（step=2 以 step=1从相遇处继续走到环口）

展开理解：

①基本解题假设：把数组看作链表。即把数组的值，看作指向下一个节点的位置，curValue=nextIndex。
②题设：index in [0,n]，value in [1,n]。

结论1：如果把数组看作链表，则一定有环。
因为：由①②，则value =下一个节点的下标 index一定成立，即没有结束条件，环∃。

③基本解题假设：根据环的定义，环内有个节点 nums[i]，直接指向环入口，即ringEnterIndex=nums[i]。

结论2：nums[0]，不在环内。
因为：由①②，没有 value 指向 0。则 nums[0] 就是环外的节点。

④基本解题假设：环∃，则可以进入到环中。
实现方式是，定义两个指针 slow，fast，
从同一个起点nums[0]，
以不同速度出发，slow步长=1，fast 步长=2，
若能相遇，即两个指针，到达同一个位置ringFirstMeetIndex，则到达的这个位置在环内。

结论3：由①④，从 环外nums[0] 开始，slow 要想和 fast 相遇，需经过环入口ringEnterIndex，进入到环内
slow的路径：从nums[0]，经过nums[ringEnterIndex]，到了 nums[ringFirstMeetIndex]。

结论4：环入口ringEnterIndex，就是我们的目标解：数组中的重复数
slow的路径应该是：从nums[0]，经过环外的节点 nums[j]，直接到nums[ringEnterIndex]，最终到 nums[ringFirstMeetIndex]。其中，ringEnterIndex=nums[j]，
又由③，ringEnterIndex=nums[i]，
则 nums[j]=nums[i]=ringEnterIndex。即这是一组重复数，值是ringEnterIndex。

⑤求 ringEnterIndex
设：
⑥d=d[0,ringEnterIndex]=d[0,nums[j]], 
d2=[ringEnterIndex,ringFirstMeetIndex]，
⑦d3=[ringFirstMeetIndex,ringEnterIndex]=[ringFirstMeetIndex,nums[i]]。
则 d+d2=d3+d2=环的长度，化简等式得 d＝d3，
d3+d2意味着从环入口ringEnterIndex，绕环走了一圈，再次到达环入口ringEnterIndex。

我们可以通过d和d3的关系⑥⑦，以相同的速度，2次相遇（secondMeet），来定位 ringEnterIndex，
环外，slow从  0 到 ringEnterIndex＝nums[j]，
环内，fast 从 ringFirstMeetIndex 到 ringEnterIndex＝nums[i]，
得出，nums[j]=nums[i]，可以解出nums[j]，
于是，ringEnterIndex的值=nums[j]。

// 题解 java 代码
// 时间复杂度 O(n)
// 空间复杂度 O(1)
class Solution {
    public int findDuplicate(int[] nums) {

        // 初始化快慢指针
        int slow = nums[0];
        int fast = nums[0];

        // 相遇，进入到环中
        while (true) {
      // 慢指针每次走一步
            slow = nums[slow];
      // 快指针每次走两步
      // nums[nums[fast]]：把数组看作链表，每个元素的值被视为（指向链表中下一个节点的）索引。
            fast = nums[nums[fast]];
      // 如果相遇，则跳出循环，表示在环中。
            if (slow == fast) break;
        }

        // 再次相遇，到达环的入口
        // 将慢指针重置为起点
        slow = nums[0]; 
        while (slow != fast) {
      // 两个指针每次走一步，直到相遇
            slow = nums[slow];
            fast = nums[fast];
        }

        // 返回重复的数字
        return slow;
    }
}