1. Two Sum

배열과 특정 값이 주어지고, 배열 안에서 두 수를 합쳐 특정 값이 나올 수 있는지 찾는 문제

* 반드시 유의미한 정답은 한개는 있다

 

예를 들어서, [1,3,5,7,9]와  6이 주어지면 [1,5]로 6을 만들수 있고, 이것들의 위치를 넘겨주면 되는 문제

 

for 두 번 돌려서 확인 가능하다.

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(0, len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

근데 for 두번이면 시간 복잡도가 n^2이므로 이것보다 빠르게 하는 방법을 찾아보면...

 

1) in을 이용한다.

-> for 한개에서 첫번째 값을 지정해놓고, 나머지값을 in으로 찾기

-> list.index(target, start, end)를 이용하면 배열 안에서 값의 위치를 찾을 수 있다. 찾을 범위도 지정 가능하다. 
-> index(target)을 해버리면 [3,3], 6에서 결과값이 [0, 0]이 되버린다. 따라서 start위치를 i+1로 지정해줘야한다. 

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            sub = target - nums[i]
            if sub in nums[i+1:]:
                return [i, nums.index(sub, i+1)]

 

2) dict를 이용한다. 

dic에 값들을 저장한 후에 in을 이용하는 방법

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i, value in enumerate(nums):
            dic[value] = i

        for i, value in enumerate(nums):
            if target - value in dic and i != dic[target-value]:
                return [i, dic[target-value]]