题目：
给定一个包含n+1个整数的数组nums，其数字在1到n之间（包含1和n），可知至少存在一个重复的整数，假设只有一个重复的整数，请找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
分析:
-
这道题没有说时间复杂度，那么既然这样就先不考虑，题目说给定一个整数数组，在1-n之间，数组有n+1个整数。
-
在这个数组里面存在着一个重复的整数，但是数组的数字是在1-n之间，我们可以最简单的情况把这个数组想为一个有序数组例如[1.2,3,3,4]
-
有了这个数组就应该有思路了，对于这个数组来说无非就是吧这个重复的3找出来。于是，这个题就有很多的解法了
解题加代码实现
解法一：快慢指针法
我们可以把数组的下标拿出来 例如这个数组：
int[] a={1,2,3,3,4}
其下标为
0 1 2 3 4 5
先定义一个下标index=0
* 将下标取的值给index
* index[0]=1
* index[index[0]]=2
* index[index[index[0]]]=3
* index[index[index[index[0]]]]=3
* 到此处时，就已经产生了循环，因为下标3的值为3，3到3循环
* 于是就产生了环
于是这个问题就成了环链表寻找环的入口
不懂什么是环链表可以参考 ：
于是就又有了快慢指针法
给定两个 一个快，一个慢
慢：slow
快：fast
slow距离换入口有x的长度
当在y的距离时候遇到到了fast
链表的总长为len
此时fast走过的距离为slow的两倍之多
此时时候
x+y 为slow走过的长度
2（x+y）=len+y
len = 2x+y
y = len-2x
然后让fast从y开始走
slow从表头开始走
当其在某个位置如k点再次相遇时候
k点为成环的起点
即为所求
具体可参考：
算法学习之双指针(java版)
代码实现：
public class Test01 {
public int findLoop(int nums[]){
int slow =0;
int fast = 0;
while (true){//遍历数组，让其第一次相遇y
slow = nums[slow];
fast =nums[nums[fast]];
if (slow == fast){//其在y点相遇
slow = 0;//slow从头开始遍历
fast = nums[nums[fast]];//fast从y继续遍历,让fast在环里继续走
while (slow != fast){//不相等，继续遍历，相等了，就停止
slow = nums[slow];
fast = nums[fast];
}
return slow;//环开始的位置，也是其题目求得重复的位置
}
}
}
解法二：异或算法
例如这个数组：
int[] a={1,2,3,3,4}
由题可得 数组的数从1-n，数组有1-n+1个
那么，在这个数组中 n =4
由异或运算可得：
1^1=0
0^0=0
1^0=1
0^1=1
相等为0，不相等为1异或运算法则:
- a ^ b = b ^ a
- a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;
- d = a ^ b ^ c 可以推出 a = d ^ b ^ c.
- a ^ b ^ a = b.
由此可推理为
a ^ 0 = a
a ^ a =0
因此由异或运算可得：
将前n个数进行异或运算，然后在n+1个数进行异或运算
因为 (a^b^c^....)^(a^b^c^...)=0
所以在此数组中
n=4
所以
int count = 1^2^3^4
int counts=1^2^3^3^4=1^2^3^4^3
因此：
count^counts = (1^2^3^4)^(1^2^3^4)^3=0^3=3
即为所求
代码实现:
public int xor_Algorithm(int nums[]){
int n = nums.length-1;
int count = 0;
int counts=0;
for (int i = 1;i<=n;i++){
count^=i;
}
for(int i = 0;i<nums.length;i++){
counts ^= nums[i];
}
return counts^=count ;
}
解法三：
使用双层循环，时间复杂度是O(n^2)
解法四：
使用hash表，set存储
我就不写三四种写法了，有兴趣的朋友可以写一写，如果我的思路或者代码有问题，欢迎大家指正纠错。