[알고리즘] #Two Sum II - Input Array Is Sorted

문제 출처: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Two Sum II - Input Array Is Sorted - LeetCode

 

문제 해석

오름차순으로 정렬된 정수형 배열이 주어졌을 때, 2개의 요소의 합이 target과 같은 index array를 리턴하라.

if (numbers[index_1] + numbers[index_2] === target){
	return [index_1, index_2]
}

이 테스트는 정답이 분명히 존재하고, 같은 원소를 2번 더하는 경우는 없다. 

 

 

풀이

이 문제는 이진 탐색으로 풀면 간단하게 풀 수 있다.

var twoSum = function(numbers, target) {
    let low = 0
    let high = numbers.length-1
    while(low < high) {
        if(numbers[low] + numbers[high] === target) {
            return [low+1, high+1]
        } else if(numbers[low] + numbers[high] > target) {
            high -= 1
        } else {
            low += 1
        }
    }
};

배열의 양 끝 index 값을 low, high으로 주고

- numbers[low] + numbers[high] > target 이면, high를 1씩 줄이고 다시 비교한다.

- numbers[low] + numbers[high] < target 이면, low를 1씩 더하고 다시 비교한다.

- numbers[low] + numbers[high] == target 이면, [low, high]을 리턴한다.