一、题目描述
这是 LeetCode 上的一道算法题：存在重复元素，难度为 简单。
Tag：「数组」、「哈希表」、「排序」
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
示例 1：
1
2
| 输入：nums = [1,2,3,1]
输出：true
|
示例 2：
1
2
| 输入：nums = [1,2,3,4]
输出：false
|
示例 3：
1
2
| 输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true
|
提示：
1 <= nums.length <= 105
-109 <= nums[i] <= 109
二、解题思路
2.1、法一
暴力求解，双重 for 循环
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public boolean containsDuplicate(int[] nums) {
if(nums == null)return false;
int length = nums.length;
for(int i = 0;i<length;i++){
for(int j = i+1;j<length;j++){
if(nums[i] == nums[j]){
return true;
}
}
}
return false;
}
}
|
时间复杂度：O(n^2)
2.2、法二
先对数组进行排序，在比较相邻的两个数是否相等，如果相等则证明有相同元素 return true，如果循环结束了没有相同元素则返回 false
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public boolean containsDuplicate(int[] nums) {
if(nums == null)return false;
Arrays.sort(nums);
int length = nums.length;
for(int i = 0;i<length-1;i++){
if(nums[i] == nums[i+1]){
return true;
}
}
return false;
}
}
|
时间复杂度：O(n)
2.3、法三
for 循环遍历，使用 HashMap 将数组的元素作为 key，索引作为 value 添加，添加之前每次判断 HashMap 是否存在了相同 key，如果存则 return true，结束循环。如果 for 循环结束了也不存在相同的 key，则 return false；
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public boolean containsDuplicate(int[] nums) {
if(nums == null)return false;
Map<Integer,Integer> integerMap = new HashMap();
for(int i = 0;i<nums.length;i++){
if(integerMap.containsKey(nums[i])){
return true;
}
integerMap.put(nums[i],i);
}
return false;
}
}
|
时间复杂度：O(n)
2.4、法四
for 循环遍历，使用 HashSet 进行重复元素的过滤，如果 HashSet add 时存在相同的元素，其会返回 false
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public boolean containsDuplicate(int[] nums) {
if(nums == null)return false;
Set<Integer> integerSet = new HashSet();
int length = nums.length;
for(int num: nums){
if(!integerSet.add(num)){
return true;
}
}
return false;
}
}
|
时间复杂度：O(n)
三、总结
本道算法题考查了我们对数组中重复元素的检测，我们使用了 4 中解题方法：
法一：双重 for 循环暴力求解，这种方式是最不可取的，时间复杂度高，效率最低
法二：这种方式调用了 JDK 给我们提供的 Arrays 进行排序，觉得不可取，我们应该自己去编写排序算法实现
法三，法四：一个使用 HashMap，一个使用 HashSet，利用它们不能重复添加元素的特性解决问题，推荐使用
好了，本篇文章到这里就结束了，感谢你的阅读🤝