[LeetCode] 1. Two Sum

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]

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than $O(n^2)$ time complexity?

My Solution

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

브루트 포스로 풀어도 되지만 Follow-up에 명시된 것처럼 시간복잡도를 $O(n^2)$ 보다 작게 만들기 위해 dictionary를 사용했다.

nums_map = {
	# num : index
    2: 0,
    7: 1,
    11: 2,
    15: 3
}

위와 같은 방법으로 dictionary를 만들고 풀면 브루트포스에서 사용하는 중첩반복문을 사용하지 않아도 된다.