[Leetcode] 1. Two Sum

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

Two Sum - LeetCode

 

Sum 문제는 크게 2가지로 나뉠 수 있다:

1. 주어진 배열에서, 몇 가지 숫자를 더해 특정 값을 얻을 수 있는지의 가능성 판단 여부 

2. 더 나아가 숫자 조합 찾기 → 이 경우 배열을 정렬하는건 좋은 아이디어는 아님..

 

 

Solution 1. Brute-force

Time: $O(N^2)$

Space: $O(1)$

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """

        for i in range(len(nums) - 1):
            a = nums[i]
            for j in range(i + 1, len(nums)):
                b = nums[j]
                if a + b == target:
                    return [i, j]

Solution 2. Dictionary (hash table)

이러한 문제에서는 hash table (Python의 경우 dictionary) 같은 자료 구조가 큰 도움이 되는 경우가 많다. 

 

Python의 in 연산자의 시간 복잡도는 다음과 같다.

• list - Average: $O(n)$
• set/dict - Average: $O(1)$, Worst: $O(n)$, but very uncommon

 

Time: $O(N)$

Space: $O(N)$

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """

        seen = dict() # key: number / value: index
        for idx, val in enumerate(nums):
            remain = target - val

            if remain in seen: # O(1)
                return [idx, seen[remain]]
            
            seen[val] = idx