Leet code 1 -Two sum

 

array 문제이다. combination 모듈 사용후 filter, index 사용을 생각해 보았으나, 그러면 o n2의 시간 복잡도를 초과하게 된다.

 

브루트 포스로도 n2의 시간 복잡도를 만족시킬 수 있다.

 

from itertools import combinations

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

        # ~을 뽑아서  타겟값을 만든다. 아웃풋으로 그 재료의 인다이스값 반환.
        # 다만 조건에서 두개만 뽑으면 됨을 말하고 있다.
        # 브루트포스? 일단 타겟보다 크거나 같은 수는 조사할 필요가 없지.
        # 라기엔 음양수가 있다. 한번 뽑은 거 또 뽑기는 안됨.
        
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

 

해쉬맵을 이용한 풀이.

 

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        d = {}
        for i, j in enumerate(nums):
            r = target - j
            if r in d: return [d[r], i]
            d[j] = i

신박하다..