[Top Interview 150 - Two Pointers] 167. Two Sum II - Input Array Is Sorted

[Q] [Medium]

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.

 

• 모르겠어서 찾아보고 풀음
• 하나 고정해놓고 하나씩 더해보려고 헀는데, 왼쪽 / 오른쪽 하나씩 줄여나가는 방법이 더 좋다는 생각이 들었다.
• l 과 r 의 + / - 는 달라지면 안된다. -> sorted 되어 있기 때문에

 

# Answer

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

        while l < r :
            s = numbers[l] + numbers[r]
            if s == target:
                return [l+1, r+1]
            elif s < target:
                l += 1
            else:
                r -= 1