[DSA][Array & Hashing] 03. Two Sum

LeetCode 1

 

03. 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.

 

 

[질문하기]

- 정수 배열에 중복된 숫자가 있을 수 있나요?

- 배열이 정렬되어 있나요?

- 정답은 단 하나라고 가정해도 될까요? or 항상 valid 한 정답이 있나요? (YES)

- 정답으로 반환해야 하는 인덱스는 정렬된 순서여야 하나요? (NO)

 

 

[아이디어]

a + b = target을 만족하는 두 수를 찾아야 하는데, 원소를 돌 때 a가 나왔다면 우리는 이후에 b가 필요하다는 사실을 알게 된다.

b가 필요하다는 것은 b를 찾아야 한다는 것이고, 특정 원소가 있는지 없는지를 탐색할 때는 hash가 유용하다.

따라서 a가 나왔을 때, b (target - a)를 key로 저장하고 a의 인덱스를 value로 저장해 놓는다면 (인덱스를 반환해야 하므로) 다음에 b가 나왔을 때 이전에 b가 필요한 원소가 있었는지를 빠르게 탐색하고 a의 인덱스와 현재의 인덱스 (b의 인덱스)를 반환할 수 있다.

반대로, 지금 원소를 저장해두고 b가 나왔을 때 이전에 a (target - b)가 있었는지를 확인하는 로직도 OK

 

 

[풀이 1] Hash

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

가끔 코드의 순서 ≠ 논리의 흐름이어서 해석하기가 어려울 때가 많은데, 위 코드에서도 if문이 나중에 실행되지만 위에 와 있어서 헷갈릴 수 있다. for문 안에서 현재 원소를 보고 필요한 원소 (target - 현재 원소)와 지금의 인덱스를 저장해 두고, 나중에 (= if) 현재 원소가 hashNum에 있다면, 이 전에 이 원소의 짝이 나왔다는 의미이므로 저장해 뒀던 짝의 인덱스와 나의 인덱스를 반환하는 것이다.

 

⏱️ 시간복잡도

배열을 한 번 순회하기 때문에 시간 복잡도는 O(n)이다.

🧠 공간복잡도

배열의 원소 개수만큼의 공간이 필요하기 때문에 공간 복잡도도 O(n)이다.

 

 

[풀이 2] Two Pointer

만약 배열이 정렬되어 있다면? Two pointer 방식을 사용하는 것이 유리할 수 있다.

Hash 풀이처럼 추가적인 hashmap이 필요하지 않기 때문에 공간복잡도가 O(1)이 되기 때문이다.

하지만 이 문제에서는 배열이 정렬되어 있지 않기 때문에 정렬(O(nlogn))을 해야 하고, 인덱스를 반환해야 하는데 정렬하는 과정에서 인덱스가 틀어지기 때문에 이를 고려해서 새로운 배열을 만들어주어야 한다.