题解 | #数组中重复的数字#

这道题的关键在于时间复杂度要求为O(n)，因此如果采用每一个元素都遍历一遍数组的话，时间复杂都就成了O(n^2)。 因此我们需要另辟蹊径，让数组中的每个元素都有一个状态（为 0 为没有遍历过，为 1 则为已被遍历过）。由于 0 <= n <= 10000，所以需要 new 一个大小为 10000 的整型数组 array 。当一个数 nums[ i ] 被遍历到时，将会把 array[ nums[ i ] ] 的值置为 1 来表示这个数已被遍历过一次了，当再次遍历到 nums[ i ] 时，就说明重复了，直接把值放回。这样时间复杂度就下降到了 O(n)。

	public int duplicate (int[] numbers) {
        int[] array = new int[10000];
        for (int i = 0; i < numbers.length; i++) {
            if (array[numbers[i]] == 0) {
                array[numbers[i]] = 1;
            }else {
                return numbers[i];
            }
        }
        return -1;
    }