217. Contains Duplicate

Leetcode

https://leetcode.com/problems/contains-duplicate/description/

題目

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example 1:

Input: nums = [1,2,3,1]
Output: true

Example 2:

Input: nums = [1,2,3,4]
Output: false

Example 3:

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

解答

• 方法一 - HashTable

Time complexity: O(n)

Space complexity: O(n)

var containsDuplicate = function(nums) {
    const map = new Map();

    for(let i=0; i<nums.length; i++) {
        const value = nums[i];
        if (map.has(value)) {
            return true;
        }
        map.set(value, i);
    }

    return false;
};

Runtime: 91 ms Beats 33.46% of users with JavaScript

Memory: 66.92 MB Beats 5.39% of users with JavaScript

• 方法二 - Sorting

Time complexity: O(nlogn)

Space complexity: O(1)

var containsDuplicate = function(nums) {
    nums.sort((a, b) => a - b);

    for(let i=0; i<nums.length; i++) {
        if (nums[i] === nums[i+1]) {
            return true;
        }
    }

    return false;
};

Runtime: 140 ms Beats 17.79% of users with JavaScript

Memory: 59.30 MB Beats 46.14% of users with JavaScript

• 方法三 - Set

直接使用原生的 Set 方法

var containsDuplicate = function (nums) {
    const s = new Set(nums)
    return s.size !== nums.length
};

參考資料

LeetCode 刷題紀錄 ｜217. Contains Duplicate (Easy)Medium

花花酱 LeetCode 217. Contains Duplicate - Huahua's Tech RoadHuahua's Tech Road