[LeetCode] 1. Two Sum

https://leetcode.com/problems/two-sum

문제 유형

배열, 해쉬 테이블

해설

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

풀이

3가지 문제 풀이 방법이 있다.

• 부르트 포스
  모든 경우의 수를 구하는 방법으로 for 문을 2개 사용한다. 시간 복잡도는 2중 for문을 사용했기 때문에 O(N^2)이다.
• Two-pass Hash Table
  모든 값을 먼저 Hash Table에 저장을 하고 (타겟 - 해당 인덱스 값)이 있는지 찾는다.
  시간 복잡도는 Hash Table에 넣는 시간 O(N) + 찾는 시간 O(N) 이다.
• One-pass Hash Table
  map을 만들어 처음부터 (타겟 - 해당 인덱스 값)이 있는 지확인하고 없으면 map에 넣어준다.
  시간 복잡도는 1번만 지나가므로 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);
     }
  };