LeetCode 217 存在重复元素（JAVA）

一、题目描述：

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1]
输出：true
示例 2：

输入：nums = [1,2,3,4]
输出：false
示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true
 

提示：

1 <= nums.length <= 105
-109 <= nums[i] <= 109

二、题目分析：

该问题针对的是数组对象。通过遍历数组，保存每个数出现的次数，我的想法是通过set，依据set集合的性质，不能添加重复的元素进行判断，如果无法添加元素，则说明已存在该元素，则返回true。否则直到遍历结束。

三、开始作答：

class Solution {
    public boolean containsDuplicate(int[] nums) {

        Set<Integer> set = new HashSet<>();

        for(int num :nums){
            //如果无法加入set，则说明存在该元素，即次数=2
            if(!set.add(num)){
                return true;
            }
        }
        return false;
    }
}

四、查看题解:

题解主要有两种解法，一种是利用set，即我考虑的方式。

此时的时间复杂度为O(N)

还有一种方式，即先对数组进行排序，然后再两两比较，如果两个元素相等，则返回true.

此时的时间复杂度由于进行了排序，为O(NlogN）

代码如下：

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/contains-duplicate/solutions/518991/cun-zai-zhong-fu-yuan-su-by-leetcode-sol-iedd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。