[LeetCode] Two Sum

LeetCode - 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

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

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

내 풀이
문제를 보고 바로 생각난 방법은 이중 for문을 이용한 brute force 를 사용한 풀이였다.

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

정답은 맞췄으나 시간 복잡도 측면에서 낮은 결과를 보여준다.

Solution을 통해 무슨 방법이 있나 봤더니 제일 첫번째이자 제일 느린 방법이 내가 푼 방법이었다.

2,3번 Solution 모두 hash table을 이용한 풀이이며 그 중 One-pass hash table을 이용한 풀이가 제일 간결하고 시간 복잡도 측면에서도 좋은 결과를 보여줬다.

class Solution:
    def twoSum(self, nums, target):
        h = {}
        for i, num in enumerate(nums):
            n = target - num
            if n not in h:
                h[num] = i
            else:
                return [h[n], i]

이중 for문은 list를 두번 순회하게 되지만 One-pass hash table을 이용한 풀이는 한번만 순회하게 된다.

One-pass hash table?
list를 순회하면서 hash table에 넣은 다음 순회하는 두번의 과정을 거치는 대신, 순회하면서 동시에 넣는 방식으로 단 한번의 순회로 hash table을 생성하는 과정

어려운 문제는 아니었으나 자주 사용하게 되는 이중 for문, brute force 의 시간 복잡도를 줄이는 방법을 생각하게 된 좋은 문제라고 생각한다.