[리트코드] 1. Two Sum

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

제한사항

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

풀이

정렬한 다음 맨 앞과 맨 뒤를 가리키는 포인터를 만든다.

각 포인터를 더한 값을 target과 비교해서 작으면 시작 포인터를 이동시키고 크면 끝 포인터를 이동 시킨다.

그런데 원래 답은 원래 배열의 인덱스로 리턴해야하므로 정렬하기 전에 배열을 변형해서 원래 인덱스를 같이 담아줬다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums = sorted([(v, i) for i, v in enumerate(nums)])
        l, r = 0, len(nums) - 1
        
        while l < r:
            if nums[l][0] + nums[r][0] < target:
                l += 1
            elif nums[l][0] + nums[r][0] > target:
                r -= 1
            else:
                return [nums[l][1], nums[r][1]]

항상 한가지의 pair가 존재한다고 했고, a +b = target이므로 a= target - b임을 이용하면 딕셔너리를 이용해서 풀 수 있다.

   def twoSum(self, nums, target):
        d = {}
        for i, n in enumerate(nums):
            m = target - n
            if m in d:
                return [d[m], i]
            else:
                d[n] = i