[DSA][Two Pointers] 02. Two Sum II - Input Array Is Sorted

LeetCode 167

 

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

 

 

[질문하기]

- 정수 배열에 중복된 숫자가 있을 수 있나요? NO

- 정답은 단 하나라고 가정해도 될까요? or 항상 valid 한 정답이 있나요? YES

 

 

[아이디어]

- Two Pointer를 사용하여 Sum과 Target을 비교하자.

 

 

[풀이 1] Two Pointer

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

이 문제에는 Hashing 카테고리에서도 나왔던 Two Sum을 구하는 문제이다. Two Sum - Hash

그때와 최적 풀이 방법이 다른 이유는, "already sorted in non-decreasing order" 조건 때문이다.

이미 배열이 오름차순으로 정렬이 되어 있기 때문에, hash가 아닌 two pointer를 사용하면 공간 복잡도를 줄일 수 있다.

 

two pointer를 양 끝으로 두고 시작한 후 두 인덱스가 가리키는 숫자의 합을 target과 비교했을 때 합이 더 크다면, R 포인터를 줄이고 합이 더 작다면 L 포인터를 늘리면 각각의 경우에 합을 줄이고 늘릴 수 있다.

 

⏱️ 시간복잡도

정수 배열을 한번 순회하기 때문에 O(n) 시간 복잡도를 갖는다.

🧠 공간복잡도

변수 공간만 필요하므로 O(1) 공간 복잡도를 갖는다.