Two Sum

https://leetcode.com/problems/two-sum/description/

1. 직관적인 풀이

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

새롭거나 신기한건 없는거 같다. 문제 조건에 두 수의 합이 타겟이 되는 조합이 하나밖에 없기에, 두 수를 뽑아 더해 타겟과 대조한다.

2. 다른 풀이
   내 방식은 시간 복잡도가 조금 크다는 단점이 있다. 이것을 사람들은 dict을 통해 탐색시간을 줄여나간다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = {}

        for i, value in enumerate(nums):
            missedNum = target - value
            if missedNum in dict:
                return [i, dict[missedNum]]

            dict[value] = i

확실히 해시 맵이 탐색에 유리한거 같기는 하다.