LeetCode : Two Sum (Easy)

0. Overview

• 풀이 날짜 : 2021-06-09
• 풀이 소요 시간 : 10m
• LeetCode URL : https://leetcode.com/problems/two-sum/

1. Problem

2. Solution

def twoSum(nums, target):
        seen = {}
        for i, v in enumerate(nums):
            remaining = target - v
            if remaining in seen:
                return [seen[remaining], i]
            seen[v] = i
        return []

3. Review

• 처음 문제를 보고서는 Brute force 알고리즘을 활용해 빠르게 문제를 해결하였으나, 시간 복잡도가 $\displaystyle\ O(n^2)$ 이므로, Leet Code 내 Solution 을 참고하여 더 나은 풀이 방법에 대한 스터디 진행하였습니다.
• LeetCode Solution 내 One-pass Hash Table 방식을 활용하면 시간 복잡도 $\displaystyle\ O(n)$ 과 공간 복잡도 $\displaystyle\ O(n)$ 으로 문제 해결이 가능합니다.
• 위 Solution 의 경우 One-pass Hash Table 방식을 활용한 문제 풀이입니다.