给定一个包含 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) 。数组中只有一个重复的数字，但它可能不止重复出现一次。这道题比较好做哈哈哈，主要思路就是新建一个数组来储存每一个数出现的次数，这样可以做到线性时间内找到出现的重复数，题目要求只有一个重复数，所以减少了很多难度，下面给出AC代码：
class Solution { public: int findDuplicate(vector<int>& nums) { int res; int n=nums.size(); int a[n]={0}; for(int i=0;i<n;i++){ a[nums[i]]++; } for(int i=0;i<n;i++){ if(a[nums[i]]>=2){ res=nums[i]; break; } } return res; } };看了一下讨论，发现学到了很多东西，下面我把讨论的内容复制粘贴在这里供学习使用
【笔记】这道题（据说）花费了计算机科学界的传奇人物Don Knuth 24小时才解出来。并且我只见过一个人（注：Keith Amling）用更短时间解出此题。
快慢指针，一个时间复杂度为O(N)的算法。
其一，对于链表问题，使用快慢指针可以判断是否有环。
其二，本题可以使用数组配合下标，抽象成链表问题。但是难点是要定位环的入口位置。
举个例子：nums = [2,5, 9 ,6,9,3,8, 9 ,7,1]，构造成链表就是：2->[9]->1->5->3->6->8->7->[9]，也就是在[9]处循环。
其三，快慢指针问题，会在环内的[9]->1->5->3->6->8->7->[9]任何一个节点追上，不一定是在[9]处相碰，事实上会在7处碰上。
其四，必须另起一个for循环定位环入口位置[9]。这里需要数学证明。
