一、问题

找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。限制：2 <= n <= 100000

示例：输入：[2, 3, 1, 0, 2, 5, 3]输出：2 或 3

二、解答

1️⃣HashSet
由于只需要找出数组中任意一个重复的数字，因此遍历数组，遇到重复的数字即返回。为了判断一个数字是否重复遇到，使用集合存储已经遇到的数字，如果遇到的一个数字已经在集合中，则当前的数字是重复数字。

初始化集合为空集合，重复的数字 repeat = -1
遍历数组中的每个元素：
将该元素加入集合中，判断是否添加成功
如果添加失败，说明该元素已经在集合中，因此该元素是重复元素，将该元素的值赋给 repeat，并结束遍历。返回 repeat。

public int findRepeatNumber(int[] nums) {
    Set<Integer> set = new HashSet<>();
    int repeat = -1;
    for (int num : nums) {
        if (!set.add(num)) {
            repeat = num;
            break;
        }
    }
    return repeat;
}

①时间复杂度：O(n)。
遍历数组一遍。使用哈希集合 HashSet，添加元素的时间复杂度为 O(1)，故总的时间复杂度是 O(n)。
②空间复杂度：O(n)。不重复的每个元素都可能存入集合，因此占用 O(n) 额外空间。

public static int findRepeatNumber(int[] nums) {
    // HashSet
    HashSet<Integer> set = new HashSet<Integer>();
    for (int x : nums) {
        //发现某元素存在，返回
        if (set.contains(x)) {
            return x;
        }
        //存入哈希表
        set.add(x);
    }
    return -1;
}

2️⃣原地置换
大体思路就是将指针对应的元素放到属于它的位置(索引对应的地方)。可以这样理解，每个人都有自己的位置，需要和别人调换回到属于自己的位置，调换之后，如果发现自己的位置上有人了，则返回。一个萝卜一个坑，由于长度为 n 的数组内所有数字都在 1~n-1，那么元素与下标之间就可以存在一一对应的关系，即将“正确”的元素放到“正确”的位置，把 0 放到 nums[0]，把 1 放到 nums[1]...如果“正确”的位置上已经存在了“正确”的元素，说明该位置的元素就是重复的元素，返回即可。如果“正确”的位置上没有存放“正确”的元素，就进行交换，将“正确”的元素放到正确的位置。

public static int findRepeatNumber(int[] nums) {
    if (nums.length == 0) {
        return -1;
    }
    for (int i = 0; i < nums.length; ++i) {
        while (nums[i] != i) {
           // 如果对应位置已经存在该元素，说明重复
            if (nums[i] == nums[nums[i]]) {
                return nums[i];
            }
            //置换，将指针下的元素换到属于它的索引处
            int temp = nums[i];
            nums[i] = nums[temp];
            nums[temp] = temp;
        }
    }
    return -1;
}

①时间复杂度：O(n)。
②空间复杂度：O(1)。

3️⃣排序
由于长度为 n 的数组内所有数字都在 1~n-1 之间，所以排序后，重复数字必然相邻，由于只需要找出任意一个重复元素即可，返回第一个相邻元素即可。

public static int findRepeatNumber(int[] nums) {
    // 排序后的数组，重复元素必然相邻
    Arrays.sort(nums);
    // 结果集
    int res = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        // 找到重复元素
        if (nums[i] == nums[i + 1]) {
            res = nums[i];
            break;
        }
    }
    return res;
}

①时间复杂度：排序是最容易想到的方式，但是由于多了一个排序过程，即使是快排，其时间复杂度也是 O(logn)，排序后还要遍历有序数组，时间复杂度 O(n)，总时间复杂度为 O(nlogn)。
②空间复杂度：O(1)。