[Leetcode] 1. Two Sum - Top Interview Questions

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

Two Sum - 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.

---

nums 정수 배열과 target 정수가 주어지면, nums의 원소들 중 두 숫자의 합이 target이 될때 그 두 원소들의 index를 반환하라.

 

주어지는 입력에서 정확히 하나의 solution이 있다고 가정할수 있으며, 한 원소를 중복해서 사용할 수 없다.

 

어떤 순서로든 답을 반환할 수 있다.

---

Constraints:

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

 

문제 해석

주어지는 배열을 탐색하여 target에 맞는 두 원소를 찾기

 

sol 1 - Brute force(완전 탐색) O(n^2)

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

가장 쉽게 접근할 수 있는 방법이지만, 확실히 느리다. 좀 더 쉬운 방법을 생각해보자.

 

sol2 - Hash O(n)

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

해쉬를 이용해서 O(n)만큼만 탐색한다. 정답은 무조건 하나 존재하므로 nums 배열의 값을 key로 가지는 해쉬라고 생각하여 nums배열을 순차적으로 탐색하며 target - x를 key로 갖는 값이 존재한다면 정답이 된다.

예를 들어보자.

nums = [1, 2, 3, 4]  target = 6

 

target - x = 6 -1 = 5

tmp = { 1 : 0 }

 

target - x = 6 - 2 = 4

tmp = { 1 : 0, 2 : 1 }

 

target - x = 6 - 3 = 3

tmp = { 1 : 0, 2 : 1, 3 : 2 }

 

target - x = 6 - 4 = 2

tmp = { 1 : 0, 2 : 1, 3 : 2} 

return [ tmp[target - x], i ] = [ 1, 3 ]