[LeetCode] 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.

풀이 

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

2개의 포인터를 잡아서 끝에서 끝으로 더해 target의 값이 나오면 return하는 방법으로 접근했는데. 아무래도 for문으로 두 번 돌다보니 runtime이 꽤 나왔다. 이번문제도 map으로 푸는 것이 좋았을뻔했다. 

 

다른풀이1

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  let rMap = new Map()
  for (let i=0;i<nums.length; i++) {
    let verschil = target - nums[i]

    if (rMap.has(verschil)) {
      return [i, rMap.get(verschil)]
    }

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

이번 문제에서 map을 사용했을 때 좋은 점은 for문을 한 번만 돌면서 map에 index별로 값을 할당해줄 수 있다는 점인데. 우선 target에서 nums[i에 해당하는 값을 빼서 어떤 숫자를 찾아야할지 결정하고 for문을 돌면서 map에 값을 넣어준다. 돌다가 map에 필요한 숫자를 발견하면 반환

다른풀이2

function twoSum(nums, target) {
    let dict = {};

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

        if (dict.hasOwnProperty(complement)) {
            return [i, dict[complement]];
        }

        dict[nums[i]] = i;
    }
}

위랑 원리는 같은데 좀 더 보기 명료한 느낌이라 따로 기록해둔다.