wo Sum - JavaScript

Two Sum

0. 문제 해결 방법

총 2가지의 해결 방법이 있다.

• Array를 사용한 완전 탐색
• Hash Table을 사용하여 한번에 탐색하는 방식

1. Array을 사용하여 완전 탐색으로 해결하는 방법

• 시간 복잡도 : O(n^2) => O(n) loop를 두 번 수행한다.
• 공간 복잡도 : O(1) => input array를 적재할 공간이 필요하지 않다.

var twoSum = function(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (target - nums[i] === nums[j]) {
        return [i, j];
      }
    }
  }
}

2. Hash Table을 사용하는 방식

• 시간 복잡도 : O(n) => O(1)인 해쉬맵을 사용하여 loop를 1회 수행한다.
• 공간 복잡도 : O(n) => value를 적재할 별도 공간(map)을 필요로 한다.

var twoSum = function(nums, target) {
  const map = new Map(); 
  for (let i = 0; i < nums.length; i++) {
  	const diff = target - nums[i]; //찾는 값 
    if ( map.has(diff) ) {
      // map에서 이전에 넣어둔 키값 중에 diff가 있는지 확인한 후 반환 
      return [map.get(diff), i]; 
    }
    map.set(nums[i], i); // [key:number, value:index] 
  }
}