题目描述：
寻找重复数
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
说明：
不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。
输入示例 1：
[1,3,4,2,2]
输出示例1：
2
输入示例2：
[3,1,3,4,2]
输出示例2：
3
题目分析：
这道题呢，可以用抽屉原理加二分的方法来做，也可以用快慢指针来做。具体代码如下~
抽屉原理加二分思路：
比如数组取值都在1~ n之间，那么如果小于等于n/2的数的个数大于n/2那么重复数一定在1~ n/2-1之间，否在n/2+1~ n之间。
快慢指针思路：
首先我们需要记住两个结论：(1) 设置快慢指针，如果有环，则快慢指针一定会相遇，没环的话快指针会最终指向null；(2) 设置快指针从头开始，慢指针从相遇的地方开始，快慢指针每次都移动一步，则他们一定会在环的入口处相遇。
这里我们把数组抽象成链表，数组的值代表链表的下一个结点的下标，如果数组有重复值的话，则会形成环。举个栗子，如下图，至此我们就可以用快慢指针的思想解决这道题啦。
数组链表环.png
代码实现：
抽屉原理+二分
class Solution {
public int findDuplicate(int[] nums) {
int n=nums.length;
int l=1,h=n-1;
while(l<=h){
int cnt=0;
int mid=l+(h-l)/2;
for(int i=0;i<nums.length;i++){
if(nums[i]<=mid) cnt++;
}
if(cnt>mid) h=mid-1;
else l=mid+1;
}
return l;
}
}
快慢指针
class Solution {
public int findDuplicate(int[] nums) {
int low=nums[0];
int fast=nums[nums[0]];
while(low!=fast){
low=nums[low];
fast=nums[nums[fast]];
}
fast=0;
while(low!=fast){
low=nums[low];
fast=nums[fast];
}
return low;
}
}
