[LeetCode 해석 및 풀이] 167. Two Sum II - Input Array Is Sorted

LeetCode 문제 해석 및 풀이 방법

 

문제 167. Two Sum II - Input Array Is Sorted(두개의 합2 - 입력 배열이 정렬)

바로가기

 

문제 설명

영문

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.

한글

1부터 인덱스가 지정되어있는 이미 오름차순으로 정렬된 정수 배열이 주어지면, 더해서 target을 만드는 두 숫자를 찾으시오. 두 숫자 numbers[index1]와 numbers[index2]는 1 <= index1 < index2 <= numbers.length.

 

두 숫자의 인덱스 index1와 index2를, 하나의 길이 2의 정수 배열 [index1, index2]로 만들어 반환하세요.

  

각 입력에는 정확히 하나의 해답이 있다고 가정하며, 같은 요소를 두 번 쓸 순 없습니다.

 

당신의 해답은 반드시 특정한 공간만을 사용해야 합니다.

 

제한조건

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

 

입출력 예

입력	출력
numbers = [2,7,11,15], target = 9	[1,2]
numbers = [2,3,4], target = 6	[1,3]
numbers = [-1,0], target = -1	[1,2]

 

 

해답 및 해설

파이썬 (Python)

Two Sum  1번 문제에서 입력 배열이 정렬된 형태로 바뀐 문제. neetcode 로드맵에서 나온대로 2-포인트를 이용하면 풀 수 있다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        f = 0
        e = len(nums) - 1

        while f<e:
            sum = nums[f] + nums[e]

            if sum > target: e-=1
            if sum < target: f+=1
            if sum == target: return [f+1, e+1]

앞쪽에 포인터 하나, 뒷쪽에 포인터 하나를 둔다. 그 후 값이 target보다 작으면 앞쪽 포인터를 큰쪽으로 옮기고, target보다 크면 뒤쪽 포인터를 작은쪽으로 옮긴다. 이 과정을 반복하여 맞는 값의 포인터를 찾는다.