Two Sum II - Input Array Is Sorted

167. Two Sum II - Input Array Is Sorted

문제

이미 정렬되어 있는 배열의 두 수 합이 target이 되는 두 요소의 인덱스를 찾는 문제이다.

정렬되지 않은 배열에서 두 수의 합이 target이 되는 요소의 인덱스를 구하는 문제는 👉 여기

테스트 케이스

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]

2와 7의 합은 9이다. 
그러므로 `index1`과 `index2`는 
각각 `1`, `2`가 되므로 `[1, 2]`를 리턴한다. 

풀이

인덱스는 1-based, 1부터 시작하므로 결과 배열에서 1씩 더해주면 된다.

left(초기값 0)와 right(초기값 legnth-1) 두 포인터를 이동하며, 두 수의 합이 target보다 클 경우 right 포인터를 왼쪽(-1)으로 이동시키고, 작을 경우 left 포인터를 이동(+1)하여 두 수의 합이 target과 같아질 때까지 반복한다. (정확히는 left와 right 포인터가 같아지기 전까지 반복하는데, 문제에서 유일한 답이 있다고 전제하고 있어서 예외처리를 따로 하진 않았다.)

시간 복잡도 O(n)이다.

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
  let left = 0;
  let right = numbers.length - 1;

  while (left < right) {
    let tempSum = numbers[left] + numbers[right];
    if (tempSum === target) {
      return [left + 1, right + 1]
    } else if (tempSum > target) {
      right--;
    } else {
      left++;
    }
  }
};