力扣-217-判断数组是否含有重复元素

评论

题目：
217. Contains Duplicate (Easy)
Given an array of integers, find if the array contains any duplicates.
Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

1
2
3
4
5
6
7
8
9
10
11
Example 1:
Input: [1,2,3,1]
Output: true

Example 2:
Input: [1,2,3,4]
Output: false   

Example 3:
Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

题目大意：
给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

解题思路：
典型哈希的应用。
首先我想到的就是用HashMap< Integer,Boolean >这个map直接存出现的键值对，注意原始类型和封装类的区别：
https://www.cnblogs.com/hello-yz/p/3712610.html
还有一种方法，这里使用集合Set，这是因为Set集合不包含重复元素,每个元素都是唯一的，与本题非常契合，详见代码。
https://blog.csdn.net/bestxiaok/article/details/78413022

还有个Set、List、HashMap的优缺点比较

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
Java:
//第一种HashMap 时间复杂度O(n) 空间复杂度O(n)
public boolean containsDuplicate(int[] nums){
    Map<Integer,Boolean> map = new HashMap<>();
    for(int i = 0;i < nums.length;i++){
        if(map.containsKey(nums[i])){
            return map.get(nums[i]);
        }else{
            map.put(nums[i],true);
        }
    }
    return false;
}

//第二种HashSet 时间复杂度O(n) 空间复杂度O(1)
//这里取巧了，不是直接判断存在，而是判断set长度和原nums长度，相等则没有重复，小于则有重复
public boolean containsDuplicate(int[] nums){
    Set<Integer> set = new HashSet<>();
    for(int num : nums){
        set.add(num);
    }
    /* 或者这样写也可以
        for(int num : nums){
        if(set.contains(num)){
            return true;
        }else{
            set.add(num);
        }
    }
     */
    return set.size() < nums.length;
}
/* 或者这样写也可以 直接判断
public boolean containsDuplicate(int[] nums){
    Set<Integer> set = new HashSet<>();
        for(int num : nums){
        if(set.contains(num)){
            return true;
        }else{
            set.add(num);
        }
    }
    return false;
}
*/

Python:

InstantCWeedStudent

个人简介。