287. Find the Duplicate Number

寻找长度为n+1数组中只重复出现一次的数字，数组范围在[1, n]

鸽巢原理/抽屉原理+二分法，算出中位index：mid，对小于等与mid的数字进行统计，若大于mid，说明左边有重复的数字（可以想成原来应该是相等的，但是有重复的数字所以超过了限制），则移动右指针为r。时间O(nlogn)，空间O(1)

public int findDuplicate(int[] nums) {
    int l = 0,  r = nums.length;
    while (l < r) {
        int mid = (l + r) >>> 1;
        int count = 0;
        for (int num : nums) {
            if (num <= mid) count++;  // count number <= mid
        }
        if (count <= mid) l = mid + 1;
        else r = mid;
    }
    return l;
}

快慢指针，同链表cycle检测#142，找entry point, 这种解法限制很大，必须同时满足n+1长度，[1, n]的大小范围（不能是0），否则出界，如测试用例[0, 2, 2, 4, 5, 6]，前面一种解法可以有0，set解法都适用。

http://keithschwarz.com/interesting/code/?dir=find-duplicate

public int findDuplicate(int[] nums) {
    if (nums.length <= 1) return -1;
    int slow = 0, fast = 0, entry = 0;
    while (true) {
        slow = nums[slow];
        fast = nums[nums[fast]];
        if (slow == fast) {
            while (entry != slow) {
                entry = nums[entry];
                slow = nums[slow];
            }
            return entry;
        }
    }
}

如果不考虑长度和范围，可以设置set并去重，时间空间均为O(n).

public int findDuplicate(int[] nums) {
    HashSet<Integer> set = new HashSet<>();
    for (int num : nums) {
        if (set.contains(num)) return num;
        set.add(num);
    }
    return -1;
}