题目描述
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2] 输出: 3
说明：
- 不能更改原数组（假设数组是只读的）。
- 只能使用额外的 O(1) 的空间。
- 时间复杂度小于 O(n2) 。
- 数组中只有一个重复的数字，但它可能不止重复出现一次。
https://leetcode-cn.com/problems/find-the-duplicate-number/
解法1
首先，题目说了不能更改数组、且空间复杂度为O(1)，那么我们就不能够使用排序算法。此外，时间复杂度要求小于O(n^2)，就不能够使用暴力法（双重循环遍历每个元素）。
题目描述了有n+1个元素，值域为[1, n]，这就提示我们：我们可以用数组内容作为数组的索引。例如nums = [1,3,4,2,2]：
索引 0 1 2 3 4
内容 1 3 4 2 2
从索引为0开始，使用数组内容作为索引遍历：
nums[0] = 1
nums[1] = 3
nums[3] = 2
nums[2] = 4
nums[4] = 2
nums[2] = 4
nums[4] = 2
......
可以看出重复序列为[2,4,2,4,...]，我们将重复序列绘制成图，如图1所示。
我们再举例nums = [3,1,3,4,2]：
索引 0 1 2 3 4
内容 3 1 3 4 2
从索引为0开始，使用数组内容作为索引遍历：
nums[0] = 3
nums[3] = 4
nums[4] = 2
nums[2] = 3
nums[3] = 4
nums[4] = 2
nums[2] = 3
nums[3] = 4
......
可以看出重复序列为[4,2,3,4,2,3,...]
我们可以看出，如果数组包含重复元素，使用数组内容作为索引会产生重复序列。我们将数组内容按照顺序绘制成图，如图2所示。
对于序列中是否重复的判定，有很多方法可以实现。在这里，我们使用Floyd’s cycle-finding algorithm来实现判圈。该算法很简单，使用快慢指针指向圈的节点，慢指针一次移动一步，快指针一次移动两步，当两个指针相遇时就可以得知存在环路。
如果数组中存在重复元素，那么将遍历序列绘制成图将会形成环路。而进入环路的起点正是数组的重复元素。为了寻找环路的起点，我们将慢指针重新移动到起点，之后，快指针与慢指针每次都只移动一步，当他们再次相遇，就是环路的起点。
下面这张图，给出了该方法能够找到环路起点的证明：
根据分析，我们能够编写出如下代码。
class Solution {
public int findDuplicate(int[] nums) {
int slow = nums[0], fast = nums[nums[0]];
// 快慢指针找到相遇点
while (nums[slow] != nums[fast]) {
slow = nums[slow];
fast = nums[nums[fast]];
}
// 将慢指针移动到起点，寻找圈的入口
slow = 0;
while (nums[slow] != nums[fast]) {
slow = nums[slow];
fast = nums[fast];
}
return nums[slow];
}
}
参考：