[leetcode] - 217. Contains Duplicate

2023-04-01 · 배운 것 · 4분 읽기

problem

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

Contains Duplicate - LeetCode

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.

Constraints:

• 1 <= nums.length <= 10^5
• -109 <= nums[i] <= 10^9

Access

1. brute force (O(n^2))
The problem has constraint (0 <= nums.length <= 10^5)
maybe run loop 10^10 on a rough estimate.

so, I think get a timeout error

function containsDuplicate(nums: number[]): boolean {
    for(let i = 0; i<nums.length; i++){
        const c1 = nums[i];

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

    return false;
};

fortunately, The solution is passed.

but, the runtime score is not good.

2. using cache O(n)
The solution needs large memory but, good runtime speed.

save the previous number. so, we don't need another for loop in first for loop.

function containsDuplicate(nums: number[]): boolean {
    //using cache O(n)
    const cache = new Map<number, boolean>();
    for(let i = 0; i<nums.length; i++){
        const currentNum = nums[i];
        
        //check! is there currentNum in cache
        const isThere = cache.get(currentNum);
        
        if(isThere){
            return true;
        }
        
        //set currentNum in cache
        cache.set(currentNum, true);
    }

    return false;
};

this solution has a good runtime.

but, use a lot of memory.