1. Two Sum

Solution

딕셔너리를 사용해 해결했다.
배열을 처음부터 끝까지 순회하면서 아래 과정을 거친다.

1. 타겟에서 자기 자신을 뺀 수, 합치면 타겟이 되는 수가 딕셔너리에 있는지를 검사한다.
   1.1. 있다면 해당 수의 인덱스와 자신의 인덱스를 반환하고 종료한다.
2. 자기 자신을 key로, 인덱스를 value로 딕셔너리에 저장한다.

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

시간 복잡도

배열 전체를 순회하고, 최악의 경우에는 가장 끝의 수에서 해답을 찾는 경우이므로 전체적인 시간 복잡도는 O(n)이다.