[Leetcode] 1. Two Sum

문제

https://leetcode.com/problems/two-sum/

풀이

먼저 O(N^2)인 브루트포스로 제출한 풀이는 다음과 같다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i,j]

이후 시간복잡도는 O(N)으로 해시테이블을 이용하여 제출한 풀이는 다음과 같다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i,j]

해시테이블을 이용하면, 추후 접근시 O(1)이 되므로 시간복잡도를 개선할 수 있어진다.

cf. Hash Table 시간복잡도 정리

worst가 n인건 hash function을 거친 결과가 모두 같은 곳을 바라보게 되는 상황으로 매우 이례적인 상황이다.
참조: https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/main/DataStructure#hash-table