[Top 75 LeetCode Questions] Two Sum (with JS)

 

서론

LeetCode에는 문제가 무수히 많기 때문에 어떤 것부터 풀어봐야할지 어려움이 많습니다. 그래서 서칭을 하던 도중 블라인드에 Facebook 엔지니어가 정리해준 75가지 LeetCode 주요 질문 리스트가 눈에 띄었고 이를 풀어보기로 결정했습니다. 저는 프론트엔드 엔지니어이기 때문에 이 문제들을 Javascript로 풀어보도록 하겠습니다.

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

문제

정수 배열 nums와 정수 target이 주어지면 두 숫자를 합한 값이 target 값이 되는 두 숫자의 인덱스를 반환하여 대상에 합산되도록 합니다.

각 입력에 정확히 하나의 솔루션이 있다고 가정하고, 동일한 요소를 두 번 사용하지 않을 수 있습니다.

어떤 순서로든 답변을 반환할 수 있습니다.

풀이

1) 브루트포스 (Brute Force)

• 시간복잡도 : O(n^2)

/**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
var twoSum = function(nums, target) {
  for (let first = 0; first < nums.length; first++) {
    for (let second = first + 1; second < nums.length; second++) {
      if (nums[first] + nums[second] === target) {
        return [first, second];
      }
    }
  }
};

2) Hash Table 2번 사용

• 시간복잡도 : O(n)

/**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
var twoSum = function(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    map.set(nums[i], i);
  }
  for (let i = 0; i < nums.length; i++) {
    let complement = target - nums[i];
    if (map.has(complement) && map.get(complement) !== i) {
      return [i, map.get(complement)];
    }
  }
  return null;
};

3) Hash Table 1번 사용

• 시간복잡도 : O(n)

/**
    * @param {number[]} nums
    * @param {number} target
    * @return {number[]}
    */
var twoSum = function(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    let complement = target - nums[i];
    if (map.has(complement)) {
      return [i, map.get(complement)];
    }
    map.set(nums[i], i);
  }
  return null;
};