题目传送门

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

算法原理

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

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

复杂度分析 

时间复杂度：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）为这个数组的长度