[LeetCode]Two Sum

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

Two Sum - LeetCode

 

문제 분석

주어진 nums 값에서 두 숫자를 골라 더해 target 값을 만드는 문제입니다.

항상 1개의 answer만이 도출됨이 보장되어 있습니다.

 

처음 시도한 답안 O(n^2)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for idx, num in enumerate(nums):
            second_num = target - num
            if second_num in nums:
                second_num_idx = nums.index(second_num)
                if idx != second_num_idx:
                    return [idx, second_num_idx]

접근 방법

1. nums를 순회하면서 target 에서 뺀 값을 구합니다.
2. second_num 값이 nums에 있다면 그 시점의 idx와 second idx를 구합니다.
3. 단, 이 때 같은 인덱스가 되지 않도록 조건을 걸어둡니다.

처음 시도한 답안의 시간 복잡도는 O(n^2) 입니다. n번 반복을 통해 순회하고 * second_num이 nums 리스트 안에 있는지 구하기 때문입니다. 우선은 정답을 맞출 수 있었으나, 문제에서 O(n^2) 아래로도 낮출 수 있다는 점이 언급되어 있어서 다른 해결책을 찾아 보았습니다.

(ps. `element in 리스트` 의 시간 복잡도는 O(n) 입니다.)

 

두번째로 시도한 답안 O(n)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """
        O(n) hasp map.
        """
        hashmap = {}
        for index, value in enumerate(nums):
            if target - value in hashmap:
                return [hashmap[target - value], index]
            hashmap[value] = index

접근 방법

1. nums를 순회합니다.
2. hasp map 안에 target - value 값이 있는지 확인합니다.
3. 있다면 hasp map안의 인덱스와, 현재의 index를 return 합니다.
4. 없다면 hasp map에 저장합니다.

두번째 방법은 hasp map을 활용하는 방법입니다. 반복문을 순회 하다보면 종료 직전의 hash map은 다음과 같이 저장되어 있습니다.

Input: nums = [3, 2, 4], target = 6

hasp_map 
{3: 0, 2: 1}

즉, 첫번째에 해당하는 num이 key, idx가 value로서 저장되어 있습니다. 그렇게 순회하다 target - value인 값이 hasp_map 안에 있다면 종료됩니다.

(ps. `element in 딕셔너리` 의 시간 복잡도는 O(1) 입니다.)