[Problem Solving with Python] LeetCode 217. Contains Duplicate

문제

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

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.

Test Case Example:

Input: nums = [1,2,3,1]
Output: true

풀이

Solution 1.

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

nums 배열을 순회하면서 각 element에 대해 hash table에 있는지 확인하고 없으면 hash table에 저장한다. hash table에 존재하면 즉시 종료하고 True를 반환하고, nums 배열을 끝까지 순회했는데 존재하지 않는다면 False를 반환한다.

Time Complexity: for loop을 1번 사용하므로 O($n$)
Space Complexity: hash table에 저장하는데 필요하므로 최대 O($n$)

Solution 2.

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

Python의 set를 이용한 풀이이다. 복잡도는 같지만 걸리는 시간을 비교해보면 2번째 풀이가 더 빠른 것으로 나타난다.

Time Complexity: set를 만드는데 O($n$) 필요
Space Complexity: 추가적인 메모리 필요 없으므로 O(1)

Full Code

Link: https://github.com/datawhales/Python-Code-Notes/blob/main/ps/leet_217_contains-duplicate_211020.py