DaleStudy | Leetcode Study 1주차 - Contains Duplicate

Leetcode Study 1주차

 

문제

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
Explanation: The element 1 occurs at the indices 0 and 3.

 

Example 2:

input: nums = [1,2,3,4]
Output: false
Explanation: All elements are distinct.

 

Example 3:

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

Constraints:

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

 

풀이

문제를 보면 중복이 있는지 없는지 확인만 하면 되기 때문에 자바스크립트 자료구조 Set을 이용해서 size와 배열 길이를 비교해주면 끝난다. 자료구조 Set의 경우, 중복된 값을 제거해주기 때문에 만약 중복이 없다면, 배열과 길이가 동일하고 중복이 있다면 배열과 길이가 다를 것이다.

 

그리고, 조건을 보면 허용 가능한 시간 복잡도와 공간 복잡도를 알 수 있다.

• 시간복잡도: O(n) 또는 O(n log n)까지 가능
• 공간복잡도: O(n)까지 가능

길이를 비교하는 경우, 배열과 Set의 시간복잡도와 공간복잡도가 동일한데 시간복잡도는 O(1), 공간복잡도는 O(n)이기 때문에 이 조건을 충분히 만족하기 때문에 아래의 방식으로 해결할 수 있다. 

function containsDuplicate(nums: number[]): boolean {
    return new Set(nums).size !== nums.length;
};

 

 

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