[LeetCode][JS] 1번 Two Sum

문제 유형

배열, 해쉬 테이블

 

문제

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

 

배열의 숫자 값을 2개 더했을 때 target값과 같다면 각 인덱스를 아무 순서에 따라 배열로 반환해라. 반드시 해답은 1개 있으며 배열의 숫자를 반복해서 사용하며 안된다. 

 

예시

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Input: nums = [3,2,4], target = 6
Output: [1,2]

Input: nums = [3,3], target = 6
Output: [0,1]

 

 

풀이

3가지 방법으로 푼다.

 

1. 부르트 포스

모든 경우의 수를 구하는 방법으로 for문 2개를 사용한다. for문 > for문 > if문(타겟과 두개 더한 값이 같은가?) 로 코드를 구성하면 된다.

 

시간 복잡도는 2중 for문을 사용했기 때문에 O(N^2)이다.

공간 복잡도는 return값 이외에 다른 저장공간을 사용하지 않았기 때문에 O(1)이다. 

 

2. Two-pass Hash Table

모든 값을 먼저 Hash Table에 저장을 하고 (타겟 - 해당 인덱스 값)이 있는지 찾는다. 

 

시간 복잡도는 Hash Table에 넣는 시간 O(N) +  찾는 시간 O(N)으로 O(N)이다.

공간 복잡도는 O(N)이다.

 

3. One-pass Hash Table

map을 만들어 처음부터  (타겟 - 해당 인덱스 값)이 있는지 확인하고 없으면 map에 넣어준다. 

 

시간복잡도는 1번만 지나가므로 O(N)이다.

공간 복잡도는 최대 n개의 요소를 저장하게 되니 O(N)이다. 

 

코드

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

 

 

// Two-pass Hash Table (JS object)
var twoSum = function (nums, target) {
  const obj = {};

  nums.forEach((item, index) => {
    obj[item] = index;
  });

  for (let index = 0; index < nums.length; index++) {
    const complement = target - nums[index];

    if (obj[complement] !== undefined && obj[complement] !== index) {
      return [index, obj[complement]];
    }
  }
};

 

 

// One-pass Hash Table
var twoSum = function (nums, target) {
  const map = new Map();

  for (let index = 0; index < nums.length; index++) {
    const complement = target - nums[index];

    if (map.has(complement)) {
      return [map.get(complement), index];
    }

    map.set(nums[index], index);
  }
};