[LeetCode] 1. Two Sum

Problem:

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.

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]

Solution:

1. Brute Force 방법

먼저 가장 간단한 방법으로 앞에서부터 순서대로 모든 경우의 수를 시도해보는 것이다. 두 번째 예시에서 보면,

3 + 2 = 5 -> x
3 + 4 = 7 -> x
2 + 4 = 6 -> o

와 같이 두 개의 for 문을 도는 방법으로, $O(n^2)$의 time complexity를 가진다.

2. HashMap을 이용한 방법

HashMap (Python Dictionary)을 사용했을 때 search time이 평균적으로 O(1)인 점을 이용하면 O(n)의 time complexity로 문제를 해결할 수 있다. 문제가 두 수의 합이 주어진 target과 일치하는 것을 찾는 것이므로 한 수가 주어졌을 때 target에서 값을 빼면 다른 한 값을 찾을 수 있다. 예를 들어, nums = [11,2,7,15], target = 9 라고 하자. 왼쪽에서 오른쪽으로 순서대로 하나씩 숫자를 검토한다고 할 때, 첫 번째 값은 11이다. 따라서 HashMap에 map = {11: 0} 와 같이 저장한다. 두 번째 값은 2인데 9 - 2 = 7 이므로 7이 map의 key 값에 존재하는지 체크하고 없으면 추가한다. (map = {11: 0, 2: 1}) 다음 수는 7이며 같은 방식으로 9 - 7 = 2 값이 map의 key값들 안에 존재하는지 확인하면 존재하므로, 현재 인덱스와 map의 2번 key에 해당하는 value 값을 return해주면 된다.

Code:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        prevMap = {}
        
        for i, n in enumerate(nums):
            diff = target - n
            if prevMap.get(diff):
                return [prevMap[diff], i]
            prevMap[n] = i
        return