思路及解答
借用Set
⾸先可能想到的做法，就是借助 set ，如果元素不存在 set 中，就将元素添加进去，如果 set
中包含该元素，就返回该元素即可。如果⼀直都没有重复的，那么最后返回 -1 。
java
public class Solution { public int duplicate(int[] numbers) { if (numbers != null) { Set<Integer> set = new HashSet<>(); for (int i = 0; i < numbers.length; i++) { if (set.contains(numbers[i])) { return numbers[i]; } else { set.add(numbers[i]); } } } return -1; } }- 时间复杂度：O(n) ，最差的情况可能遍历完所有的元素
- 空间复杂度： O(n) ，最⼤需 要set ⼤⼩为 n
借助数组
可以直接借助数组，因为所有数字都在 0 到 n-1 的范围内，⽤⼀个⼤⼩为 n 的数组，就可以对所有的数字进⾏统计个数，如果个数超过 1 ，那么肯定是重复的数字，如果没有重复的数字，则返回 -1 ；
java
public class Solution { public int duplicate(int[] numbers) { if (numbers != null) { int[] nums = new int[numbers.length]; for (int i = 0; i < numbers.length; i++) { if (nums[numbers[i]] == 1) { return numbers[i]; } else { nums[numbers[i]] = 1; } } } return -1; } }同样这种做法的时间复杂度和空间复杂度都是 O(n) ,并没有优化太多。
那么有没有空间复杂度为O(1) 的做法呢？
操作原数组（最优）
不借助额外的空间，那么就只能操作原数组了。如果没有重复的情况，那么这些数字排序后，数字i 和数组下标i 应该是⼀⼀对应的。不会出现多个数字i 的情况。
基于这个原则，在遍历数组的时候，将元素 i 调整到下标 i 的位置，如果下标i的位置已经有元
素，那么说明冲突了，这个元素肯定是重复的，否则继续调整后⾯的。如果没有发现重复的数字，就返回 -1 。
java
public class Solution { public int duplicate(int[] numbers) { int i = 0; while(i < numbers.length) { if(numbers[i] == i) { i++; continue; } if(numbers[numbers[i]] == numbers[i]) return numbers[i]; int tmp = numbers[i]; numbers[i] = numbers[tmp]; numbers[tmp] = tmp; } return -1; } }但是上⾯的做法，不适合求解多个重复数字的例⼦，因为调换的时候，很容易将后⾯的数字换到前⾯去，就会导致求解出来不是第⼀个重复的数字（可以⽤来求解任意的重复数字），可能是第2，3... 或者其他的重复数字。譬如： [6,3,2,0,2,5,0] 正确的解应该是 2 ，但是由于第⼀次把 6 和最后
的0 调换了位置，就会导致求解出来的值为 0 。
