[Leet Code Top 100] #1. Two Sum

문제 정보

• Leet Code 문제 링크
• 난이도 : easy

 

해결 방법

첫 시도에는 단순히 이중 for loop 를 사용하여 O(n^2) 의 시간이 걸리게 구현을 했습니다. Follow-up 에서 아래와 같이 더 빠른 풀이법을 요구했기 때문에 다른 방식의 풀이가 필요했습니다.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

value 를 찾기 위해 index 를 모두 순회하여 O(n) 의 시간이 걸리는 Array 대신 맞는 key 값을 찾는데 O(1) 의 시간이 걸리는 Map 자료구조를 사용했습니다. key 는 덧셈에 사용할 숫자, value 는 index 입니다.

map 에 두 개의 key 가 다 들어 있지 않더라도 뒤에 있던 index 에서 앞에서 이미 map 에 넣었던 key를 찾을 수 있기 때문에 이렇게 구현이 가능합니다.

 

소스 코드

// Leet Code
// #1. Two Sum
// Success
// Runtime: 80 ms, faster than 80.07% of JavaScript online submissions for Two Sum.
// Memory Usage: 41.4 MB, less than 18.03% of JavaScript online submissions for Two Sum.

function main(){
    // Input
    nums = [2,7,11,15], target = 9;
    // Output
    // [0,1]
    console.log(twoSum(nums, target));
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
// var twoSum = function(nums, target) {
//     const result = [];
    
//     for(let idx = 0; idx < nums.length - 1; idx++){
//         for(let jdx = idx + 1; jdx < nums.length; jdx++){
//             if(nums[idx] + nums[jdx] == target){
//                 result.push(idx);
//                 result.push(jdx);
//             }
//         }    
//     }
    
//     return result;
// };

// use map because 
// map : O(1)
// array's for loop : O(n)
var twoSum = function(nums, target) {
    const map = new Map(); // key : number / value : idx
    let answer = [];

    nums.forEach(function(item, index){
        let left = target - item;
        if(map.has(left)){
            answer = [map.get(left), index];
        }
        map.set(item, index);
        //console.log(`item:${item} / index:${index}`);
    } );

    return answer;
};

main();

 

참고 자료

• LeetCode Top 100 Problem Selection
• [JS #5] ES6 Map(), Set()