[코딩 테스트] 리트코드 1 - Two Sum (Easy) in Python

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.

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

주어진 숫자들의 배열 nums와 target 숫자가 주어졌을 때, 배열 안의 두 수가 더해져서 target숫자를 만드는 경우의 인덱스를 반환하라.

 

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]

 

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

Two Sum - LeetCode

 

풀이

1) 무작정 풀기

쉽지만 비효율적인 방법이다.

x + x' = target

일 때, 

배열 안에서 이중 loop를 돌리면서, x가 결정되었을 때, 배열 안 나머지 숫자 중에 x의 보수인 x'가 존재하는 지 탐색한다.

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

 

 

시간 복잡도는 O(n^2)이 되고, constraints가 작게 주어졌기 때문에 통과가 되긴 된다.

이미 주어진 배열 자체를 쓰기 때문에 공간 복잡도는 O(1)이다.

 

2) 해시 테이블 사용

탐색 시간을 상수 시간으로 줄이기 위해, 보수를 해시 테이블에 넣는 방법을 사용해보자.

해시테이블 (Hash Table) 이란?
(Key, Value)의 형태로 자료를 저장하는 구조이며,
Key값은 해시 함수를 통해 유일한 index로 바뀌어 값을 탐색 및 저장하게 된다.

index가 충돌 (hash collision)하지 않는 이상
해시 테이블 탐색의 시간 복잡도는 상수 시간 O(1)이 된다.

해시 테이블. (출처 - 위키피디아)

배열을 탐색하면서,

현재 숫자의 보수가 hash table에 이미 있다면 결과값을 리턴하고,

아니면 현재 숫자를 hash table에 넣어줘 미래의 탐색의 기반이 되도록 한다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashTable = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hashTable:
                return [i, hashTable[complement]]
            hashTable[nums[i]] = i

배열을 한 번만 탐색하므로 시간 복잡도는 O(n) * 해시 테이블에서의 탐색 O(1) = O(n)이 된다!

다만 공간 복잡도는, 새로운 해시 테이블을 만들어야 되기 때문에 O(n)이 된다.