[ 알고리즘 ] LeetCode 167. Two Sum II - Input Array Is Sorted

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 167. 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.

제약사항

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

풀이

접근법

투 포인터(Two Pointer) 접근을 통해 문제를 해결할 수 있다.

입력되는 numbers 배열이 이미 오름차순 정렬되어 매개변수로 넘어오기 때문에 단순히 반복문을 수행하며 만약 두 수의 합이 대상이 되는 값보다 클 경우 우측 인덱스를 한 칸 줄이고 클 경우 좌측 인덱스를 한 칸 늘리면 된다.

나의 풀이

접근법을 토대로 문제를 해결하면 아래와 같다.

def solution(numbers: list[int], target: int) -> list[int]:
    left, right = 0, len(numbers)-1
    while left < right:
        sum_of_two_numbers: int = numbers[left] + numbers[right]
        if sum_of_two_numbers == target:
            return [left+1, right+1]
        elif sum_of_two_numbers > target:
            right -= 1
        else:
            left += 1

시간 복잡도

양쪽 끝에서 점점 범위를 줄여나가기 때문에 최악의 경우에도 길이가 N인 배열의 모든 요소를 한 번만 확인하면 되기 때문에 시간 복잡도는 O(N)이다.