Two sum

문제설명

twoSum이라는 함수는 정수 nums의 배열과 target인 합이 되는 목표값이 인자로 주어지고 주어진 배열에서 target에 맞는 2개의 숫자의 인덱스를 반환하는 함수를 작성하기.

작성코드

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let map = new Map();

    for(let i = 0 ; i< nums.length; ++i){
        if(map.has(target-nums[i])){
            return [map.get(target-nums[i]),i]
        }
        else{
             map.set(nums[i],i)
        }
    }
    
    return []
};

해결방안

brute force 방법으로 모든 쌍의 number들을 탐색하여 찾아낼수 있지만 이 방법은 시간복잡도가 느리고 제출 시에 타임초과가 발생할 수 있다.

가장 이상적인 방법은 target에서 숫자 하나를 지정한 x값이 있고 target-x = y를 만족하는 보수를 찾아가는 것.

map 객체를 이용해서 키,값을 저장하고 키로 nums[i]로 설정하고 값으로 인덱스로 설정해 nums 배열을 돌면서 map함수의 has를 이용해 보수값이 map에 존재하면 두 쌍을 찾았으므로 두개의 인덱스배열을 반환하면된다.