LeetCode - 1. Two Sum

요즘은 LeetCode나 HackerRank를 많이 푼다길래 LeetCode easy 난이도 부터 정복을 시작하였다!

문제링크

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

Two Sum - LeetCode

문제를 설명하자면 주어진 nums 배열에서 2가지 수의 합으로 target을 만들어 내야한다.

답이 되는 2가지 수의 배열의 index를 return 하는 문제이다.

 

답안코드

1. O(n^2) 해결방법

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

사실 이 문제의 핵심은 O(n)으로 푸는 방법을 찾는건데 그냥 귀찮아서 O(n^2)으로 풀었다.

풀고 나서 discuss란을 들어가보니 O(n)으로 푸는 해결법들이 나와있었는데 대부분이 map을 사용하는 방법이었다.

 2. O(n) 해결방법

const twoSum = (nums, target) => {
  const map = {};

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

    if (another in map) {
      return [map[another], i];
    }

    map[nums[i]] = i;
  }

  return null;
};

nums 배열을 돌면서 target에서 해당 숫자를 빼 준 다음 그 숫자가 map 안에 있으면 해당 숫자의 인덱스를 리턴 해주는 방법이다.

저런 식으로 map에 { num1:index1, num2:index2 ... } 방식으로 넣어주고 사용하는게 좋은 방법인 것 같았다.