217 存在重复元素

一、题目

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

二、题解

2.1 哈希集合

思路： 利用集合元素唯一的特性，遍历数组依次将每个元素加入 HashSet。add 方法在元素已存在时返回 false，因此一旦插入失败就说明出现了重复元素，返回 true；遍历结束都未失败则说明无重复，返回 false。

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            // 尝试将元素加入 set 中。
            // 如果 set 已经包含该元素，add 方法会返回 false
            if (!set.add(num)) {
                return true;
            }
        }
        return false;
    }
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$

2.2 排序

思路： 先对数组排序，使得相等的元素彼此相邻。然后线性扫描，只需比较每一对相邻元素 nums[i] 与 nums[i+1]，若发现相等则存在重复，返回 true；扫描结束仍无相等的相邻元素则返回 false。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        if(nums.length <= 1) return false;
        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(\log n)$