[LeetCode] 1. Two Sum

*알고리즘 스터디에 참여하면서 Blind 75 LeetCode Questions 목록에 있는 문제를 풀이합니다. 

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

Two Sum - LeetCode

풀이: 

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_dic = {}
        # Stores the dictionary key as a given number value and the value as an index.
        for i, num in enumerate(nums):
            nums_dic[num] = i
            
        # Search the result of subtracting the first number from target by key
        for i, num in enumerate(nums):
            if target - num in nums_dic and i != nums_dic[target - num]:
                return nums.index(num), nums_dic[target - num]

타겟에서 첫 번째 수를 빼면 두 번째 수를 바로 알아낼 수 있다. 

먼저, 주어진 숫자의 값을 키로 하는 딕셔너리에 인덱스를 값으로 저장해서 해시 테이블을 만들어둔다.
그런 다음 타겟에서 첫 번째 수를 뺀 값이 딕셔너리에 존재하고, 첫 번째 수와 인덱스가 다르다면
첫번째 수의 인덱스와 우리가 찾은 값의 인덱스를 결과값으로 반환하면 된다. 

브루트 포스로 전체 배열을 조회해서 풀이할 경우 시간 복잡도는 O(n\(^{2}\))이다. 
위에 풀이 방법의 경우는 평균적으로 O(1)에 가능하고 최악의 경우에 O(n)이 된다.