[Leetcode] Two Sum

문제

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

 

Example 1:

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Output: Because nums[0] + nums[1] == 9, we return [0, 1].

 

Example 2:

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

utput: [1,2]

 

Example 3:

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

Output: [0,1]

풀이

Brute Force

# 브루트 포스법 
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        tmp = 0
        
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                tmp = nums[i] + nums[j]
                if tmp == target:
                    return [i, j]

Runtime: 20 ms, faster than 99.95% of Python online submissions for Two Sum. Memory Usage: 13.6 MB, less than 19.58% of Python online submissions for Two Sum.

Hash table - enumerate 사용한 경우

AIHolic 유투브 영상보고 이해한 해시 테이블 코드 - https://www.youtube.com/watch?v=VNoyfbsM83U

# 해시 테이블 - enumerate 사용
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        d = {v:i for i, v in enumerate(nums)} # 해시 테이블 
        for i, num in enumerate(nums):
            num2 = target - num
            if num2 in d and d[num2] != i: # 자기 자신 아니면서, dictionary 안에 있어야 함
                j = d[num2]
                return [i, j]

Runtime: 28 ms, faster than 92.72% of Python online submissions for Two Sum. Memory Usage: 13.5 MB, less than 47.87% of Python online submissions for Two Sum.

Hash table - enumerate 사용하지 X 경우

# 해시 테이블 - enumerate 사용 X
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        d = {nums[i]:i for i in range(len(nums))} 
        for i in range(len(nums)):
            num2 = target - nums[i]
            if num2 in d and d[num2] != i: 
                j = d[num2]
                return [i, j]

Runtime: 24 ms, faster than 99.10% of Python online submissions for Two Sum. Memory Usage: 13.4 MB, less than 75.85% of Python online submissions for Two Sum.

해시 테이블을 활용한 방법으로 해도 for문이 2번 사용되긴 하는데 하고 enumerate라도 없애지면 성능이 개선될까 했지만, 시간 복잡도와 공간 복잡도 두개 다 큰 차이가 없었다. 

이론 

Brute Force ⇒ 일반적으로 이중 for문 사용하는 코드

• 시간복잡도: O(n^2)
• 공간복잡도: O(1)

Hash table  ⇒ 딕셔너리로 표현 가능

https://baeharam.netlify.app/posts/data%20structure/hash-table

해시 테이블이란 해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조를 말한다. 기본연산으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있다.

• key값을 주소로 사용하는 테이블
• Two-pass Hash Table
  • 시간복잡도: O(n)
  • 공간복잡도: O(n)
• One-pass Hash Table
  • 시간복잡도: O(n)
  • 공간복잡도: O(n)

다른 사람들 풀이 기록: https://bortfolio.tistory.com/122