LeetCode 1 - Two Sum (Easy)

문제

LeetCode - 1번

풀이 과정

문제는 두 수의 합으로 target 값을 만들어내는 경우를 찾는 것입니다.

저는 브루트 포스 를 사용하여 모든 두 숫자 조합을 만들어본 다음 답을 찾아냈습니다.

문제 해설에서는 해시 테이블 을 사용하는 방법도 있었는데 이는 모든 수를 인덱스 값과 함께 해시 테이블 에 저장한 뒤
(target - 배열의 각 숫자) 에 해당하는 수가 해시테이블 에 존재하는지 여부를 따져
시간복잡도를 줄이는 방법도 제시하고 있습니다.
만약 (target - 배열의 각 숫자) 가 현재 해시테이블 에 존재한다면 그대로 답을 만들어 반환하고
존재하지 않으면 현재 인덱스의 값을 해시 테이블 에 추가해줍니다.

코드

브루트 포스

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

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) {
        ans = [i, j];
        return ans;
      }
    }
  }
};

Map 을 사용한 방법

var twoSum = function (nums, target) {
  const map = new Map();

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

    if (map.has(remain)) {
      return [map.get(remain), i];
    }

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