Leetcode 알고리즘 스터디 (two sum)

 

Leetcode 알고리즘 스터디 (two sum)

문제정보

[Two Sum] Description

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.

Solution (Python)

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

num_to_index = {}	num_to_index라는 딕셔너리를 초기화합니다. 이 딕셔너리는 입력으로 전달되는 각 숫자를 Key로, 해당 숫자의 인덱스를 Value로 저장합니다.
num_to_index[num] = idx	입력으로 전달받은 전체 숫자에 대해서 순회하며 딕셔너리에 저장합니다. 초기에는 딕셔너리에 저장된 key-value pair가 없기 때문에 첫번째 입력값을 Key로 넣고 해당 입력값의 리스트 index를 Value로 저장합니다.
if target - num in num_to_index:     return [num_to_index[target-num], idx]	문제는 2개의 숫자의 합을 확인하기 때문에 새롭게 확인하는 target에서 새롭게 입력되는 숫자를 뺀 값이 딕셔너리에 있다면 이 두개의 숫자의 합이 target과 같습니다. 답은 항상 1개가 존재한다고 했기 때문에 모든 입력 숫자에 대해서 한번씩 확인하면 답을 얻을 수 있습니다.