217 存在重复元素

题目

给定一个整数数组，判断是否存在重复元素。

如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例 1:

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

示例 2:

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

示例 3:

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

题解

1. 使用哈希表来储存出现过的值，如果已经存在，则直接返回 true。

TIP

执行用时：104 ms, 在所有 JavaScript 提交中击败了 42.62% 的用户
内存消耗：44.9 MB, 在所有 JavaScript 提交中击败了 6.08% 的用户

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    let hash = {} // 用来储存出现过的值
    for(let i=0;i<nums.length;i++) {
        let item = nums[i] // 当前值
        // 如果存在，则返回 true
        if(hash[item] != undefined) return true
        hash[item] = item
    }
    // 如果都没有，则返回 false
    return false
};

• 时间复杂度： `O(n)`，使用 for循环 进行了一次遍历
• 空间复杂度： `O(n)`，使用了哈希表来储存出现过的元素
• 最好情况： 较早的出现了重复的元素，则直接返回 true
• 最坏情况： 没有重复元素出现，需要等到遍历结束，返回 false

2. 使用 set 数据结构，原理同上

TIP

执行用时：88 ms, 在所有 JavaScript 提交中击败了 80.16% 的用户
内存消耗：42.4 MB, 在所有 JavaScript 提交中击败了 57.61% 的用户

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    let set = new Set()
    for(let i=0;i<nums.length;i++) {
        let item = nums[i]
        if(set.has(item)) return true
        set.add(item)
    }
    
    return false
};

• 时间复杂度： `O(n)`，使用 for循环 进行了一次遍历
• 空间复杂度： `O(n)`，使用了 Set 来储存出现过的元素
• 最好情况： 较早的出现了重复的元素，则直接返回 true
• 最坏情况： 没有重复元素出现，需要等到遍历结束，返回 false

3. 利用数组的下标原理，来查找这个元素是否存在

TIP

执行用时：96 ms, 在所有 JavaScript 提交中击败了 59.76% 的用户
内存消耗：44.5 MB, 在所有 JavaScript 提交中击败了 9.02% 的用户

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    let list = []
    for(let i=0;i<nums.length;i++) {
        let item = nums[i]
        if(list[item] != undefined ) return true
        list[item] = item
    }
    
    return false
};

• 时间复杂度： `O(n)`，使用 for循环 进行了一次遍历，查找数组是否存在元素为 `O(1)`
• 空间复杂度： `O(n)`，使用了数组来储存出现过的元素
• 最好情况： 较早的出现了重复的元素，则直接返回 true
• 最坏情况： 没有重复元素出现，需要等到遍历结束，返回 false

4. leetcode 评论看到的解法，通过比较去重后数组的长度和原来的长度进行对比

TIP

执行用时：104 ms, 在所有 JavaScript 提交中击败了 42.61% 的用户
内存消耗：43.7 MB, 在所有 JavaScript 提交中击败了 19.4% 的用户

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    return Array.from(new Set(nums)).length !== nums.length
};

• 时间复杂度： `O(n)`，`Array.from` 内部使用了遍历的方法
• 空间复杂度： `O(n)`，使用了 set 来储存元素
• 最好情况：
• 最坏情况：