当前位置：首页 > article >正文

LeetCode217——存在重复元素

article 2024/11/15 9:13:27

LeetCode217——存在重复元素

1.题目描述：

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

在这里插入图片描述

2.Result01(暴力解)

两层for循环：

public static boolean containsDuplicate(int[] nums) {
        //暴力解 会超时
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }

结果是对的，但是时间复杂度O（N2）跑出来会超时哈哈哈。
在这里插入图片描述

3.Result02（先排序、后比较）

在这里插入图片描述
相对于暴力解来说降低了时间复杂度。

 public static boolean containsDuplicate(int[] arr){
        //先排序 在比较 一次for就行
        Arrays.sort(arr);
        for (int i = 0; i < arr.length-1; i++) {
            if (arr[i]==arr[i+1]){
                return true;
            }
        }
        return false;
    }

4.Result03（哈希）

在这里插入图片描述

Set集合中无序且不能存在重复元素利用这一特性解决此题。

在这里插入图片描述
相对于排序后在比较的解法，哈希法又降低了时间复杂度——（O（N））。

public static boolean containsDuplicate(int[] arr){
        //Set集合无序 且 不能有重复元素！
        HashSet<Integer> hashSet = new HashSet<Integer>();
        for (int i:arr) {
            if (! hashSet.add(i)){//add()方法的返回值是boolean类型的  成功添加 true 未成功 false
                return true;
            }
        }
        return false;
    }