[Leetcode/파이썬] 167. Two Sum II - Input Array Is Sorted

Two Sum II - Input Array Is Sorted

---

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

 

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

 

Constraints:

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

 

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1

        while left < right :
            
            if target - numbers[right] ==  numbers[left] :
                return [left + 1, right + 1]

            elif target - numbers[right] > numbers[left] :
                left += 1
            
            else :
                right -= 1

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        while left <= right :
            res = numbers[left] + numbers[right]
            if  res == target :
                return [left + 1, right + 1]
            elif res > target :
                right -= 1
            else :
                left += 1

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        hashmap = {}
        for i, n in enumerate(numbers) :
            if target - n not in hashmap :
                hashmap[n] = i
            else :
                return [hashmap[target-n] + 1, i + 1]

첫 번째, 두 번째 코드는 사실상 같은 코드이며 수식마저 같은 코드이다. 두 번째 코드에서 while left <= right 를 빼야했는데 왜 안 뺐지...? 어쨌든 무조건 정답이 성립하는 것이 있으니 상관없을 것이다. 마지막 코드는 리트코드의 1번 문제. Two Sum 문제의 풀이방법을 변형하여 구현한 코드이다. 사실 두 코드 다 무난하게 잘 돌아가지만, 시간복잡도 상에 있어서는 1, 2 번 코드가 더 적합하다고 생각한다. 그러나 아래로 한다고 해서 안 돌아가는 것은 아니니 잘 모르겠으면 일단 생각나는대로 구현해보자. 나는 가장 아래의 코드로 풀었고, 이후 정답을 찾아보다가 위 코드의 존재를 알게되었다. 

그럼 Two Sum 문제와 어떤점에서 차이가 있을까. 이 문제는 numbers 가 오름차순으로 "정렬"되어 있다. 그렇기 때문에 투포인터를 활용하여 문제를 해결하기 아주 적합하다.

그러나 Two Sum의 경우, 정렬이 되어 있지 않기 때문에 해시맵을 활용하여 문제를 해결하는 것이 적합하다.