给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。
示例 1：
输入：nums = [1,3,4,2,2] 输出：2
示例 2：
输入：nums = [3,1,3,4,2] 输出：3
示例 3：
输入：nums = [1,1] 输出：1
示例 4：
输入：nums = [1,1,2] 输出：1
提示：
- 2 <= n <= 3 * 104
- nums.length == n + 1
- 1 <= nums[i] <= n
- nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
进阶：
- 如何证明 nums 中至少存在一个重复的数字?
- 你可以在不修改数组 nums 的情况下解决这个问题吗？
- 你可以只用常量级 O(1) 的额外空间解决这个问题吗？
- 你可以设计一个时间复杂度小于 O(n2) 的解决方案吗？
题目大意：n+1个数，有1个数字重复了多次，找出来。要求不能用额外的空间，不能改变数组内容。
解题思路：第一想法是排序，但是这要么要改变数组内容，要么需要额外的空间。
考虑如下的一个序列：
从idx=0开始，对应的val是下一个idx，建立一个类似链表的结构， 1->3->2->4->2 将会出现一个环，之后就是链表判环的解法，可以用快慢指针来做。环的入口就是重复的数字。
下面简单分析一下，因为现在肯定存在重复的数字，假设重复的数字的个数有两个，分别对应的idx为x,y ，那么肯定存在一个值为x的 和 nusm[x] 相连，也肯定存在一个值为y的 和 nums[y]相连, 这个nums[x]==nums[y]就是重复数字，也是环的入口。
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 = nums[0]; // fast是0,不是nums[0] while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; }
暴力 先排序，有相同的 肯定在一起
class Solution { public int findDuplicate(int[] nums) { List<Integer> list = new ArrayList<Integer>(); for(int i=0;i< nums.length;i++) { list.add(nums[i]); } Collections.sort(list); int pre= list.get(0); for(int i=1;i<list.size();i++) { if(pre == list.get(i)) { return pre; } pre=list.get(i); } return 0; } }