[LeetCode] 217. Contains Duplicate

217. Contains Duplicate

Easy

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

 

Constraints:

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

---

문제 풀이

• 주어진 숫자 배열에서 숫자들이 중복되는지 확인하는 문제이다.
• 제한 사항을 보면 배열의 최대 길이가 10^5이다. 
• 시간복잡도 O(N)으로 풀 수밖에 없는 조건이다. 
• 숫자를 하나씩 보면서 중복이 각각 존재하는지 보려면 적어도 O(N^2)의 시간복잡도가 걸린다. 
• 그래서 O(1) 시간에 데이터를 저장하고 확인해볼 수 있는 Hash Table 접근 방법을 사용한다. 
• 미리 숫자를 set 에 저장하고 하나씩 돌아가면서 이미 있는 숫자이면 True를 리턴하는 방법이다.
• set은 딕셔너리와는 달리 어떤 데이터를 중복되지 않게 저장해놓는 자료구조이다. 
• 1, 1, 2, 2를 set에 넣으면 1, 2 만 남는다. 
• set은 주로 중복되지 않는 데이터를 저장하여 메모리사용을 줄여 사용하는데 쓰며, 데이터를 쓰고 읽는 속도 O(1)로 빠르다.
• for 문을 돌다가 리턴을 하는 이유는 중복이 이미 존재하면 나머지 숫자를 모두 확인할 필요가 없기 때문이다.
• for 문이 끝나고 false를 리턴하는 이유는 이미 배열의 숫자들을 다 확인했는데 중복이 없다는 뜻이기 때문이다. 

소스 코드

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        hash_table = set()
        for num in nums:
            if num in hash_table:
                return True
            hash_table.add(num)
        return False