LeetCode 0001. 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 thesameelement 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 <= 10³
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• Only one valid answer exists.

해결방법

2중 for문을 사용하면 쉽게 가능하기는 하지만 시간 복잡도가 O(n²)가 되기 때문에 다른 방법을 생각해야 했다.
두 번째로 생각했던 방법은 target - num 결과의 숫자가 존재하는지 확인하고 해당 숫자의 인덱스를 가져오려고 했는데, 문제의 세 번째 예시를 해결하는 데 어려움이 있었고, 결국 해시 테이블을 사용하여 O(n)으로 문제를 해결할 수 있었다.

from typing import List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict_nums = {}
        for index, num in enumerate(nums):
            rest = target - num
            # target에서 num을 뺀 숫자가 해시 테이블에 존재할 경우
            if rest in dict_nums:
                return [dict_nums[rest], index]
            # 그 외의 경우
            else:
                dict_nums[num] = index