287. Find the Duplicate Number

Difficulty: Medium

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n²).
There is only one duplicate number in the array, but it could be repeated more than once.

不允许修改数组，只允许使用 O(1) 的空间，也就无法使用排序、HashMap/HashSet统计的方法。

1. 二分查找

利用平均值来进行二分查找。求出1-n的平均值，根据小于平均值的元素个数是否超出来判断重复值在左侧还是右侧，然后递归得到最终的重复值，但是这种方式对于有不连续的数据无法AC

[1,4,2,2,5,6,7,8]

2. 快慢指针

这个数组中的所有值都是小于数组长度的，可以把这些值看成链表中的next索引。由于有重复的数字指向同一个元素，所以一定会存在环状索引，且环的起始位置就是重复的数字。
此时顺利的将问题转化为对环起始点的检测，即：

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

287. Find the Duplicate Number