217. 存在重复元素

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

题解1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean containsDuplicate(int[] nums) {
    //使用集合存储，每次存入数据时进行判断，如果集合里面已经包含该元素，则返回true
    //如果不包含该元素，则存入集合
    Set<Integer> set = new HashSet<>();

    for (int i = 0; i < nums.length; i++) {

        if (set.contains(nums[i])) {
            return true;
        } else {
            set.add(nums[i]);
        }
    }
    return false;
}
  • 时间复杂度:O(N)
  • 空间复杂度:O(N)

题解2：

1
2
3
4
5
6
7
8
9
10
11
12
public boolean containsDuplicate(int[] nums) {
    //使用排序，排序完成后重复元素肯定是相邻的
    //使用两个连续的指针进行对比，若相同则直接返回true

    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            return true;
        }
    }
    return false;
}
  • 时间复杂度：O(N log N)，排序所需的时间复杂度
  • 空间复杂度：O(1),没有用到额外空间，若深究，Arrays.sort(nums)使用到了栈空间，为O(log N)