题目传送门

方法一：暴力解法（超时）

算法原理

双重循环，每次固定一个数，再遍历别的数。比较这两个数是否相等，

若相等则返回这个数。就是重复数。

复杂度分析 

时间复杂度：O（N方）

空间复杂度：O（1）

代码：

class Solution {
    public int findDuplicate(int[] nums) {
        int n = nums.length;

        for(int i = 0; i < n-1; i++){
            for(int j = i+1; j < n; j++){
                if(nums[i] == nums[j]){
                    return nums[i];
                }
            }
        }
        return -1;
    }
}

 

方法二：哈希表（数组模拟）

算法原理

建立一个大小为n的数组，用来模拟哈希表。

以各个数字作为下标，来统计各个数字出现的次数。

最终遍历这个哈希数组，若有大于1的数，则返回这个下标就是重复出现的数字。

代码：

class Solution {
    public int findDuplicate(int[] nums) {
        int n = nums.length;
        int[] hash = new int[n];

        for(int i = 0; i < n; i++){
            hash[nums[i]]++;
        }

        for(int i = 0; i < n; i++){
            if(hash[i] > 1){
                return i;
            }
        }
        return -1;
    }
}

复杂度分析 

时间复杂度：O(N) 为这个数组的长度

空间复杂度：O（N）为这个数组的长度

 方法三：哈希表（HashSet）

算法原理

创建HashSet这个哈希表。遍历数组，如果这个数字在哈希表中出现了，那么就返回这个数

如果没有出现，那么就将这个数添加到哈希表中。

class Solution {
    public int findDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();

        for(int n : nums){
            if(seen.contains(n)){
                return n;
            }
            seen.add(n);
        }
        return -1;
    }
}

 复杂度分析

时间复杂度：O(N) 为这个数组的长度，遍历的时候为n次

空间复杂度：O（N）为这个数组的长度