[LeetCode] Contains Duplicate- Python

217. Contains Duplicate

문제 링크

구분

Array, Hash, Set

풀이 요약

Hash table에 각 원소를 저장하고 이미 저장된 원소가 다시 불리면 True를 반환하고, 끝까지 순회를 마쳤다면 중복되는 원소가 없기 때문에 False를 반환한다.

나의 풀이

# Hash
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        num_dict = {}
        for num in nums:
            if num in num_dict:
                return True
            else:
                num_dict[num] = 1
        return False

# set
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(nums) != len(set(nums))

배운 점

중복되는 원소를 구할 때 Hash와 set 함수를 이용하는 풀이 방법을 알게 되었다. 이제는 구현에서 끝나는 것이 아니라 Complexity를 생각하는 습관을 들여보려고 한다.

Hash와 set 풀이의 효율성 비교

• Hash
  Time Complexity: for loop을 1번 사용하므로 O(n)
  Space Complexity: hash table에 저장하므로 최대 O(n)

• Set
  Time Complexity: O(n) (n개의 요소 조회 O(n), 해시 테이블에 맵핑 O(1))
  Space Complexity: 추가 메모리 필요 없으므로 O(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

Example 2

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

Constraints

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