[LeetCode] 167. Two Sum II - Input Array Is Sorted | LIM

문제

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Two Sum II - Input Array Is Sorted - LeetCode

 

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.

 

Example1

Input: numbers = [2,7,11,15],
target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

 

Example2

Input: numbers = [2,3,4],
target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

 

Example3

Input: numbers = [-1,0],
target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

 

설명

주어진 numbers 배열에서 합이 target이 되는 숫자 2개를 구하면 된다.

 

 

푼 방식(Two Pointer)

1. 처음 인덱스와 마지막 인덱스 설정

2-1. 두 원소 합이 target 보다 작을 경우 처음 인덱스를 한칸 뒤로 이동

2-2. 두 원소 합이 target 보다 클 경우 마지막 인덱스를 한칸 앞으로 이동

3. 두 원소 합이 target 과 같을 경우 return

 

위 방식은 이미 array 가 정렬되어 있기 때문에 풀 수 있는 방식이다. Two Pointer 방식은 여기저기서 많이 활용되니 암기하고 있으면 좋다

 

코드

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

 

결과