[Two Pointers] Two Sum II - Input Array Is Sorted

167. Two Sum II - Input Array Is Sorted

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 
 * Runtime	: 66 ms
 * Memory	: 42.38 MB
 */
var twoSum = function(numbers, target) {
  const ans = [];

  let lp = 0;
  let rp = numbers.length - 1;

  while(lp < rp) {
    const sum = numbers[lp] + numbers[rp];

    if(sum > target) {
      rp -= 1;
    }else if(sum < target) {
      lp += 1;
    }else {
      ans.push(lp + 1);
      ans.push(rp + 1);
      break;
    }
  }

  return ans;
};

전형적인 two pointers 방법을 사용하였습니다.

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

2-1. Using binary search

해답의 전문은 링크를 확인해주세요.

/*
 * Runtime	: 64 ms
 * Memory	: 42.85 MB
 */
function binary_search(arr, target, L = 0, R = arr.length - 1) {
  while (L < R) {
    let mid = ~~(L / 2 + R / 2);
    arr[mid] < target ? (L = mid + 1) : (R = mid);
  }
  return L === R && arr[L] === target ? L : -Infinity;
}
var twoSum = function (sa, t) {
  let n = sa.length;
  for (let i = 0; i < n; i++) {
    let search = t - sa[i];
    let L = binary_search(sa, search, 0, i - 1);
    if (L !== -Infinity) {
      return [L + 1, i + 1];
    }
  }
  return [-1, -1];
};

double tilde(~~) 연산자를 처음 보아서 선정하였습니다. 본 해답에서 double tilde의 역할은 Math.floor() 메소드의 역할과 동일합니다.