[Problem Solving with Python] LeetCode 1. Two Sum

문제

Link: https://leetcode.com/problems/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.

Test Case Example:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

풀이

Solution 1.

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]

가장 생각하기 쉬운 간단한 풀이로 Brute Force를 이용한 풀이이다. nums 배열을 한 번 순회하면서 각 element에 대해 target - element 값이 존재하는지 찾는다.

Time Complexity: for loop을 2번 사용하므로 O($n^2$)
Space Complexity: 추가적인 메모리가 필요 없음 -> O(1)

Solution 2.

def twoSum_2(self, nums: List[int], target: int) -> List[int]:
    nums_pair = {}
    for i in range(len(nums)):
        nums_pair[target - nums[i]] = i
    for i in range(len(nums)):
        if nums[i] in nums_pair and nums_pair[nums[i]] != i:
            return [i, nums_pair[nums[i]]]

첫 번째 풀이는 배열을 이중 for loop을 반복하여 순회하기 때문에 시간 복잡도 측면에서 비효율적으로 보인다. 두 번의 for loop 중 한 번은 인덱스와 그 인덱스에 해당하는 값을 이용하기 위해 쓰인다고 생각할 수 있다. 따라서 배열의 값과 인덱스를 함께 저장할 수 있는 효율적인 방법을 생각해보면 hash table을 생각할 수 있다. Hash table에 값이 있는지 확인할 때는 O(1)의 시간 복잡도가 사용되기 때문에 배열에서 값이 있는지 확인하는 것보다 효율적일 것이다.
두 번째 풀이는 2번의 iteration loop을 각각 돌림으로써 해결하는 방식이다. 첫 번째 iteration loop을 통해 hash table에 target - nums[i] 값을 인덱스와 함께 저장한다. 두 번째 iteration loop을 돌면서 hash table에 원하는 값이 있는지 확인한다.

Time Complexity: O(2n) -> O(n)
Space Complexity: item 수만큼 hash table에 저장하므로 정확히 O(n)

Solution 3.

def twoSum_3(self, nums: List[int], target: int) -> List[int]:
    nums_pair = {}
    for i, n in enumerate(nums):
        if n in nums_pair:
            return [nums_pair[n], i]
        nums_pair[target - n] = i

두 번째 풀이에서 2번의 iteration loop을 각각 돌림으로써 해결하였는데, 각 loop에서 값을 저장하고, 확인하는 작업을 따로 했다면, 세 번째 풀이에서는 이를 한 번의 loop을 통해 동시에 진행함으로써 좀 더 효율적으로 해결한다. Iteration loop을 돌면서 hash table에 값을 저장하는 동시에, 원하는 값이 현재까지 저장된 hash table에 존재하는지 확인하는 방식이다. 원하는 값을 찾았다면 즉시 종료하여 시간을 줄일 수 있다.

Time Complexity: O(n)
Space Complexity: 최대 O(n)

Full Code

Link: https://github.com/datawhales/Python-Code-Notes/blob/main/ps/leet_two-sum_211011.py