存在重复元素

题目地址：https://leetcode-cn.com/problems/contains-duplicate/

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

示例 1：

1
2
输入: [1,2,3,1]
输出: true

示例 2：

1
2
输入: [1,2,3,4]
输出: false

示例 3：

1
2
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

题目信息

输入： 整数数组

输出： 布尔（数组是否有重复元素）

思考

这一题比前几题都要简单，第一想法就用set存值会有成功与否判断来简单解决，不用工具类的话还有暴力比较那就是双指针比较采用嵌套循环，还有一种就是排好序再比较重复就是挨个了使用当前位置比较上一个只需要一次遍历。

代码总结

1
2
3
4
5
6
7
8
9
10
//方法一
public boolean containsDuplicate(int[] nums) {
    Set set = new HashSet();
    for(int i = 0; i < nums.length; i++){
        if(!set.add(nums[i])){
            return true;
        }
    }
    return false;
}

空间复杂度：使用了set空间占用小于等于n，为O(n)
时间复杂度：就一次遍历为n次，为O(n)

1
2
3
4
5
6
7
8
//方法二
public boolean containsDuplicate(int[] nums) {
    Arrays.sort(nums);
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == nums[i - 1]) return true;
    }
    return false;
}

空间复杂度：没用额外空间，为O(1)
时间复杂度：有排序约nlogn次、有遍历为n次，为O(nlogn)。主要取决于排序的时间复杂度，平均最好的就是快排nlog2n

1
2
3
4
5
6
7
8
9
//方法三
public boolean containsDuplicate(int[] nums) {
    for (int i = 0; i < nums.length-1; i++) {
        for (int j = i+1; j < nums.length; j++) {
            if (nums[j] == nums[i]) return true;  
        }
    }
    return false;
}

空间复杂度：没用额外空间，为O(1)
时间复杂度：双层遍历，外层遍历为n次，内层遍历次数逐步减少为小于n^2次，为O(n^2)

总结

总体来说就是两种思路：一个利用set存值不容纳重复、一个就是扫描比较，在扫描比较中使用先排序的方式优一点点