Find the Duplicate Number

O(n)的解法, 将duplicate number可以看成是链表, 比如序列 1,2, 3, 4, 2, 2 对应的index是0, 1, 2, 3, 4, 5. 1会跳转到2, 2会跳转到3, 3会跳转到4, 4会跳转到5...

1----> 2----> 3----> 4---->(2) 5 ----> (2), 跳转会2, 自行脑补

代码部分就和linked list cycle II一样了.

int findDuplicate3(vector<int>& nums)
{
    if (nums.size() > 1)
    {
        int slow = nums[0];
        int fast = nums[nums[0]];
        while (slow != fast)
        {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        fast = 0;
        while (fast != slow)
        {
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }
    return -1;
}