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(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

方法0:

思路：

1. brute force. 2. 排序O(nlogn)，再遍历找到邻居相同的数字，3. 借用find first missing positive的方法，将每个数字放到自己rightful位置，如果该位置已经有正确的数字，break并返回该数字。这几种方法都不满足复杂度的要求。

方法1: binary search

思路：

找到mid，遍历一遍统计小于mid的cnt，如果cnt <= mid，说明重复在[mid+1, n]之间，如果cnt > mid说明重复在[1, mid]之间

方法2：

思路：

用Linked List Cycle II的方法来做。这个讲解比较清晰：https://blog.****.net/monkeyduck/article/details/50439840, 这篇给出了数学解释：http://bookshadow.com/weblog/2015/09/28/leetcode-find-duplicate-number/。 举个例子：[4,6,5,1,3,2,5,7]，遇到重复数字时，fast每次循环会停在原地不动。直到slow
追赶上。此时第一次循环结束。再将另一根指针t重新由原点开始出发，当它与slow再相遇时的地点，就是重复数字的地点。因为从第一篇文章中我们得知(a + c + x) = 2 (a + x), 所以a + x = c, 所以so = xo。慢指针此时所在点为x，另一指针t从s出发，两者将在o相遇。

[4,6,5,1,3,2,5,7]
过程如下：

1. slow = 0, fast = 0
2. slow = 4, fast = 4 , 3
3. slow = 3, fast = 1, 6
4. slow = 1, fast = 5, 2
5. slow = 6, fast = 5, 2
6. slow = 5, fast = 5, 2
7. slow = 2, fast = 5, 2

退出第一次循环，进入第二次循环

1. slow = 2, fast = 0
2. slow = 5, fast = 4
3. slow = 2, fast = 3
4. slow = 5, fast = 1
5. slow = 2, fast = 6
6. slow = 5, fast =5

退出第二次循环，查询结果是5，duplicated numbers。

Complexity

Time complexity: O(n)
Space complexity: O(1)

易错点

1. 不能用while (slow != true )， 循环一开始就进不去，除非排除slow = fast = 0的情况

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0;
        
        while (true){
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) break;
        }
        
        fast = 0;
        
        while (true){
            slow = nums[slow];
            fast = nums[fast];
            if (slow == fast) break;
        }
        
        return slow;
    }
};