leetcode 알고리즘 - TwoSum

1. 문제 소개

• 배열, 해시 테이블을 이용해야 하는 문제에 속한다.
• leetcode 에서도 난이도 easy 수준의 문제다.
• 최근 블라인드에 이 문제에 대한 이야기가 인기글로 올라와서, 풀어봤다. 

2. 코드

#Runtime: 60 ms, faster than 83.47% of Python3 online submissions for Two Sum.
#Memory Usage: 15.3 MB, less than 42.38% of Python3 online submissions for Two Sum.


class Solution:


    # Brute Force - 가장 단순한 접근 -> time complexity : (n2), space complexity : o(1)
    def twoSum(self, nums,target):

        target_indices = []

        for i in range(0,len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i] + nums[j] == target:
                    target_indices+=[i,j]
                    return target_indices

        return target_indices


    # Two - pass Hash Table -> time complexity : (n), space complexity : o(n)
    def twoSum(self, nums,target):
        hash_map = {}
        target_indices = []
        # 자료구조를 해시 맵으로 생성
        for idx,va in enumerate(nums):
            hash_map[va]=idx
        
        # look up 
        for idx,va in enumerate(nums):
            minus_value = target - va
            if minus_value in hash_map and hash_map[minus_value] != idx:
                target_indices+=[idx,hash_map[minus_value]]        
                break
        
        return target_indices


    # One pass hash Table -> time complexity : (n), space complexity : o(n) 
    def twoSum(self, nums,target):
        hash_map={}

        for idx,va in enumerate(nums):
            minus_value = target-va
            if minus_value in hash_map:
                return [idx,hash_map[minus_value]]
            
            hash_map[va]=idx

    def test(self):
        nums = [2,1,94,3,-2]
        target = 92
        result = self.twoSum(nums,target)
        print(result)



if __name__ == '__main__':
    s = Solution()
    s.test()

 

3.코멘트

• 난 첫 번째 Brute Force 라고 부르는 방식으로 문제를 풀었다.  (심플한 방법을 제일 좋아하기도 하고, 저 방법이 가장 먼저 떠올랐다. )
• leetcode는 문제 제출에 대한 피드백이 비교적 잘 되있다. (시각화나, 해설, discussion도 있고..)
• 첫 번째 방식보다, 해시 기반의 자료구조를 이용했을때 시간복잡도가 매우 낮았다.
• 해시 맵을 만드는 방법도 생각을 안 한건 아니었지만, 해시 맵을 만든다고 하더라도, nums 배열의 full scan 비용  * 해시 맵 안에서 key 를 scan 비용을 더 하면 O(N2) 이 될거라고 생각했는데 아니었다. (해시 맵안에서는 키를 순회하는게 아니라 맵에 키가 있는지만 보면 되니까.. -_-; ) 
• Hash를 이용하면 Lookup 시간을 O(n) 에서 O(1)로 줄일 수 있다.