[리트코드] 167. Two Sum II - Input Array Is Sorted

19 Dec 2021 in 코딩테스트 on 리트코드

167. Two Sum II - Input Array Is Sorted

나의 풀이

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (numbers, target) {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] + numbers[j] === target) return [i + 1, j + 1];
    }
  }
};

console.log(twoSum([2, 7, 11, 15], 9));

저번에 풀었던 two Sum 문제와 굉장히 유사한 문제다.
ouput 값만 index+1 해주면 끝!

나의 풀이 (two pointer로 풀기)

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

첫번째 풀이는 효율성이 좋지 못하다. (O(n^2))
따라서 투포인터로 변경하여 효율성을 높여보았다.