描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1

数据范围： $0 \leq n \leq 10000$

进阶：时间复杂度 $O (n)$ ，空间复杂度 $O (n)$

示例1

输入：

[2,3,1,0,2,5,3]

返回值：

说明：

2或3都是对的

思路

首先是如何检测数组中有重复变量，由于题目说只需找出有重复变量的即可，不需要这个变量的重复数量是最多的，这就省去了很多功夫。

第一种最容易想到的方法就是类似于冒泡排序的双重for循环，取出数组第一个元素，依次和后面每个相比，如果相等直接赋值给result，缺点就是双重for循环的时间复杂度比较高，当数组元素过多时耗时比较大
```
loop:
for (int i = 0; i < numbers.length; i++) {for (int j = i + 1; j < numbers.length; j++) {if (numbers[i] == numbers[j]) {result = numbers[i];break loop;}}
}
```
注意这里给第一个for循环起名loop，因为如果在第二个for循环里直接使用break结束的是里层的for循环，即找到了结果还需要继续剩下的循环过程。如果指定结束外层循环loop就可以使程序运行结果更快。
第二个想到的办法是使用Set，因为Set有个函数 contains(Object o) ，只需一次for循环依次将变量加到Set中，如果Set中已有这个元素则说明这个元素重复，则输出结果。
```
Set<Integer> numberSet = new HashSet<>();
for (int i = 0; i < numbers.length; i++) {if (numberSet.contains(numbers[i])) {result = numbers[i];break;} else {numberSet.add(numbers[i]);}
}
```

然后判断不合法输入。题目说：所有数字都在0到n-1的范围内，因此比较笨的方法就是一个一个判断数组里面有没有不合理的数，有的话将结果赋值为1。

int result = numbers[0];
for (int i = 0; i < numbers.length; i++) {if (numbers[i] < 0 || numbers[i] >= numbers.length) {result = -1;}
}

但是后来有个样例没通过时发现当输出空数组时也算作不合理的输入，此时也应该输出-1，所以一开始就直接将结果赋值为-1

int result = -1;

一开始我觉得那个for循环判断可以省去，但是当输入的数组是下面这种情况时就会输出错误结果

numbers={1,5,5,2,3}

即重复的元素是不合理的输入数据，此时result结果应该为5，因为5是重复数据，但是5是不合理的数据，所以最后还是得加for循环来检测是否有不合理数据，有的话再将输出结果改为-1。

完整代码

由于线上编程只需要完成方法内完成的部分，即如下：

public int duplicate (int[] numbers) {// write code hereint result = -1;Set<Integer> numberSet = new HashSet<>();for (int i = 0; i < numbers.length; i++) {if (numberSet.contains(numbers[i])) {result = numbers[i];break;} else {numberSet.add(numbers[i]);}}for (int i = 0; i < numbers.length; i++) {if (numbers[i] < 0 || numbers[i] >= numbers.length) {result = -1;}}return result;}