[LeetCode] 1. Two Sum

I. Description

문제 링크: https://leetcode.com/problems/two-sum/description/?envType=problem-list-v2&envId=hash-table&

---

II. Code

i)

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

가장 쉽게 떠올릴 수 있는 방법이다. 하지만 첫 번째 for loop이 n-1번 반복하고, 두 번째 for loop까지 생각하면 시간복잡도는 O((n-1)+(n-2)+...+1) = O(n^2)이 나온다. 더 효율적인 방법을 떠올려보자.

 

ii)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        complement_dict = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in complement_dict:
                return [complement_dict[complement], i]
            complement_dict[num] = i

HashMap(dictionary)를 활용한 방법이다. 위 문제사진의 첫 번째 예시로 생각해보면, 처음에 2가 들어가면 target 값 9에서 7이 부족하므로 이를 dict의 key로 저장하면 나중에 조회할 때 편하겠다고 생각했다. 나중에 7을 찾았을 때 원래 2가 있었던 인덱스가 필요하므로 이를 dict의 value 값으로 저장해주었다. 그리고 HashMap의 삽입 및 조회는 시간복잡도가 O(1)이므로 이 구조를 사용하였다. 이렇게 코드를 작성하면 전체 시간복잡도가 O(n)이 된다.