Visits: 149

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

这道题在没有限制的情况下做法有很多种，例如排序，然后找到 a[i] == a[i + 1]的，或者，桶排序，记录一下每个数出现了几次。

但是题目增加了很多限制条件

• 不能更改原数组（假设数组是只读的）
• 只能使用额外的 $O(1)$ 的空间
• 时间复杂度小于 $O(n^2)$
• 数组中只有一个重复的数字，但它可能不止重复出现一次

一开始想似乎是没有思路，但是如果把题目稍作变换，马上就可以变成很熟悉的题型。

数组长度是 n + 1，这意味着数组下标是 0 ~ n，同时，数组中的数的范围是 1 ~ n，因此，数组中元素的值的取值范围是数组下标取值范围的子集。

那么，如果把数组想象成一个不存放内容、只有指针的链表，数组元素的值是当前下标的后一个链表结点下标。举例来说，a[1] = 3，那么可以认为，标号为 1 的结点的 next 是编号为 3 的结点，即 node1 -> next = node3，类似地，如果 a[2] = 4, a[4] = 5，那么这个链表就是 node2 -> node4 -> node5。

这样一来，问题就换成了，给定一个链表，链表中有一个环，问，环的起点在哪？

典型的双指针问题。

至于，为什么链表一定有环，这是由题意显然的，那么，为什么所求的答案就是环与直线的交点？

简单说，就是：快指针走过 a + b + c + b，慢指针走过 a + b，又 2(a + b) = a + b + c + b，所以c = a。

详细的证明可以参考：https://blog.csdn.net/u013077144/article/details/81070415，以及https://blog.csdn.net/monkeyduck/article/details/50439840

代码如下：

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

这里的

 while (slow != fast) {
    slow = nums[slow];
    fast = nums[nums[fast]];
}

就相当于链表写法中的

while (fast->next != nullptr && fast->next->next != nullptr) {
    fast = fast->next->next;
    slow = slow->next;
    if (fast == slow) break;
}