two sum

문제

접근 및 풀이

2중 for문으로만 생각했는데 풀이를 보니 속도가 O(1)인 객체탐색을 통해 O(n)으로 풀 수 있는 문제였다. 

코드

/* two sum */

/* user code */
function answer(nums, target) {
  let map = {}
  for (let i = 0; i < nums.length; i++) {
    const rest = target - nums[i];
    if (map[rest] !== undefined) {
      return [map[rest], i];
    }
    map[nums[i]] = i;
  }
}

/* main code */
let input = [
  // TC: 1
  [[2, 7, 11, 15], 9],

  // TC: 2
  [[3, 2, 4], 6],

  // TC: 3
  [[3, 3], 6],
];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1} `);
  console.log(answer(input[i][0], input[i][1]));
}

출처

zero-base 연습문제