리트코드(LeetCode) - 1. Two Sum

사이트 링크
문제 링크
난이도: 하

코드

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

하지만 이 방법으로는 오래 걸렸다는 결과가 나왔다.

그래서 좀 찾아보며 실행해 봤다.

그 중에서 해쉬맵(HashMap)이란 것을 찾게 되었다.
기본적으로 리스트의 모든 쌍을 비교하는데에는 $O(n^2)$의 시간복잡도를 갖고 있지만 딕셔너리 함수는 $O(n)$의 시간복잡도를 갖는다.

코드

# 해시맵을 사용한 Two Sum
num_map = {}  # 값을 키로, 인덱스를 값으로 저장
for i, num in enumerate(nums):
    complement = target - num  # 현재 숫자와 더해서 target이 되는 값
    if complement in num_map:
    	return [num_map[complement], i]
    num_map[num] = i # 없으면 num_map에 데이터 삽입

이렇게 하면 한 번의 순환으로 값을 찾아낼 수 있다!