two sum

# 찾아야 될건 더해서 target 숫자와 일치하는 숫자의 index

# 임의로 리스트의 0번째 index 부터 시작한다고 가정해보면

# target  = nums[0] + x

# x 에 해당하는 값이 nums[1:] 에 있는지 확인
# ( 사실 nums 에서 조회해도 되지만 이미 0 번째 index 를 조회 했기 때문에 index 0 은 조회할 필요가 없으므로 index 1부터 조회 )
# 있으면 해당 index 를 조회한 후 리턴

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

        for index, number in enumerate(nums):

            rest = target-number

            if rest in nums[index+1:]:

                return [index, nums[index+1:].index(rest)+(index+1)]

# 미리 숫자를 키로하고 index 를 value 로 하는 dictionary 를 만들어 놓고
# 최종적으로 리턴할 때 해당 숫자로 dictionary 에서 조회하여 시간복잡도를 낮춤

# 위에서는 nums[index+1:].index(rest)+(index+1) 으로 조회하니 O(n) 이 되지만
# 아래에서는 nums_map[rest] 으로 O(1) 임

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

        nums_map = {}
        for index, num in enumerate(nums):
            nums_map[num] = index

        for index, num in enumerate(nums):
            rest = target-num
            # index !=nums_map[rest] => [3,2,4] -> [0,0] 이 되는 것을 방지
            # index 가 중복이 되지 않도록
            if rest in nums_map and index != nums_map[rest]:
                return [index, nums_map[rest]]