217. Contains Duplicate (Array, Hash Table, Sorting)

링크 - https://leetcode.com/problems/contains-duplicate/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

해시 테이블, sorting, set 등 풀 수 있는 방법이 많다.

Code

# Hash Table
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        hash_table = {}
        for i, num in enumerate(nums):
            if num in hash_table:
                return True
            hash_table[num] = i

        return False
        
# Sorting
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()

        for i in range(len(nums) - 1):
            if nums[i] == nums[i+1]:
                return True

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

Complexity

Time Complexity: O(n) O(nlogn) for sorting approach

Space Complexity: O(n) O(1) for sorting approach