287. Find the Duplicate Number

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.

Note:

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

思路：

要理解这道题，先要理解题目142：https://blog.jing.do/5371。

把这个array看成linkedlist，快慢两个指针，如果没有重复的，他们永远碰不到，如果有重复，fast的指针会卡在那边，等待slow的指针，从而碰面。

碰到之后，从初始（最后或者最前）开始遍历，让两者交汇，交汇的值就是重复的。

如果很难理解，先理解142。

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[nums.length-1];
        int fast = nums[nums[nums.length-1]-1];
        while(slow != fast){
            slow = nums[slow-1];
            fast = nums[nums[fast-1]-1];
        }
        slow = nums.length;
        while(slow != fast){
            slow = nums[slow-1];
            fast = nums[fast-1];
        }
        return slow;
    }
}