[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이 주어졌을 때, 두 개의 숫자를 더하면 target이 되는 인덱스들을 반환해야한다. 각 입력은 정확히 하나의 해결책을 가지며, 동일한 요소를 두 번 사용하지 않아야 합니다. 답변은 어떤 순서로든 반환할 수 있습니다.

Example 1:
Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: 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]

풀이

1. Brute Force

알고리즘

brute force는 다른 말로 무차별 대입이라고 부른다.

배열의 각 요소 x를 참조한 다음, 배열에 보수(target - 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[j] == target - nums[i]:
                    return [i, j]

 

복잡도

• 시간 복잡도: O(n^2)
• 공간 복잡도: O(1)

 

2. Two-pass Hash Table

알고리즘

Hash Table을 사용하면 보다 효과적으로 배열의 보수(complement)가 존재하는지 확인할 수 있다.

첫 반복문 에선 각 요소의 값을 Key로 저장하고, 인덱스를 Value로 저장한다.

그 다음, 두번째 반복문에서 각 요소의 보수(target - nums[i])가 Hash Table에 존재하는 지 확인한 다음,

만약 존재한다면 현재 i의 값과 보수의 인덱스 값을 반환 해 주면 된다.

이 때, 동일한 요소를 중복으로 사용하면 안되므로 찾고자 하는 보수의 인덱스가 자기 자신인지도 확인해야한다.

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

 

복잡도

• 시간 복잡도: O(n)
• 공간 복잡도: O(n)

시간복잡도가 O(1)이지 않나?라고 생각할 수도있지만, 최악의 경우 중복되는 값이 많다면 O(n)이 될 수 있기 때문이다.

Hash Table에 배열의 요소를 저장하므로 공간 복잡도는 O(n)이다.

 

3. One-pass Hash Table

알고리즘

먼저 설명한 Two-pass는 Hash Table에 삽입이 다 끝난 다음, 보수가 있는지 확인하는 방법이였다.

그에 반해, One-pass는 보수가 있는지 확인한 후, 없으면 Hash Table에 값을 저장하는 방식이기 때문에 반복문 하나로 끝낼 수 있다.

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

 

복잡도

• 시간 복잡도: O(n)
• 공간 복잡도: O(n)