力扣217-存在重复元素

一、原题题目

1.1 题目

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

1.2 示例

• 示例1：

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

• 示例2：

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

• 示例3：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/contains-duplicate/

二、解题思路

2.1 HashMap思路解题

• 解题思路

  此题很简单，只需要把数组里的每一个元素依次放入哈希表中，以元素为 key ，个数为 value。只要碰到该元素已经存在与哈希表中，则可返回 true，如果能遍历完还没返回结果则最后返回 false。

• 详细代码（Java）

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i =0;i<nums.length;i++){
            if (map.containsKey(nums[i]))   return false;
            else map.put(nums[i],1);
        }
        return true;
    }
}

  上述代码中规中矩，对于一个稍微有点计算机基础的人来说没有任何难度。

• 代码执行结果

  结果好像很惨说明还有其它更优的方法。赶紧再思考思考

2.2 HashSet思路解题

  看别人题解用的同样的思路，但是用的是 HashSet 性能提升了不少

• 详细代码（Java）

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int x : nums) {
            if (!set.add(x)) return true;
        }
        return false;
    }
}

• 代码执行结果

2.3 排序思路解题

• 解题思路

  在对数字从小到大排序之后，数组的重复元素一定出现在相邻位置中。因此，我们可以扫描已排序的数组，每次判断相邻的两个元素是否相等，如果相等则说明存在重复的元素。

• 详细代码（Java）

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

• 代码执行结果

  此题结束，还是排序算法结果可以些。