LeetCode 167. Two Sum II - Input Array Is Sorted - python

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/?envType=study-plan-v2&envId=top-interview-150

• 난이도: medium
• 알고리즘: two pointer

접근방법

• 오름차순으로 정렬됨 -> 이 조건을 어떻게 활용할지 생각해본다.
• numbers의 숫자들은 중복이 없고 반드시 두 수를 합하여 targer이 되는 쌍이 존재
• 가장 첫 인덱스 idx1, 가장 마지막 인덱스를 idx2라고 하자.
• numbers는 오름차순으로 정렬돼 있으므로 idx1번째 값과 idx2번째 값의 합이 target보다 크면 idx2를 하나씩 감소시킨다.
• 만약 두 값의 합이 target이라면 해당 인덱스를 반환하고, 아니라면 idx1을 1 증가시킨다.
• 두 인덱스 쌍을 찾을 때까지 반복한다.

소스코드

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

        while idx1 < idx2:
            num1 = numbers[idx1]
            while num1 + numbers[idx2] > target:
                idx2 -= 1

            if num1 + numbers[idx2] == target:
                return [idx1 + 1, idx2 + 1]
            else:
                idx1 += 1