[LeetCode] 167 | Two Sum II | Input Array Is Sorted | Python

---

문제 링크: https://leetcode.com/problems/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$[index_1]$ and numbers$[index_2]$ where 1 <= $index_1$ < $index_2$ <= numbers.length.

Return the indices of the two numbers, $index_1$ and $index_2$, added by one as an integer array [$index_1$, $index_2$] 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.

---

조건

• 2 <= numbers.length <= 3 * $10^4$
• -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.

---

내 풀이

포인터 두개, array의 맨 앞(s)과 맨 뒤(e),를 사용한다.

numbers[s]+numbers[e]가 target보다 작다면 그 수를 키워야하기 때문에 s를 하나 증가시키고,

target보다 크다면 그 수를 줄여야하기 때문에 e를 하나 줄이고 s는 0으로 초기화시킨다.

문제에서 target을 만족시키는 s와 e의 쌍은 단 한가지만 존재한다했기 때문에 이 풀이가 가능하다.

---

코드

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        s, e = 0, len(numbers)-1
        
        while numbers[s]+numbers[e] != target:
            sums = numbers[s]+numbers[e]
            if sums < target:
                s += 1
            elif sums > target:
                s = 0
                e -= 1
                
        return [s+1, e+1]