LeetCode) Two-Sum

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

 

 

최초에는 단순하게 이중루프로 풀었다.

var twoSum = function(nums, target) {
    const result = [];
    for(let i = 0; i < nums.length - 1; i++){
        for(let j = i + 1; j < nums.length; j++){
            if(nums[i] + nums[j] === target){
                result.push(i);
                result.push(j);
                break;
            }
        }
    }
    return result;
};

 

 

통과는 하였는데

다른사람들과 실행속도가 너무 많이 차이나는데?

 

문제 맨 하단에 다음과 같은 문구가 있었다.

 

개선의 여지가 있어 보인다.

 

 

js의 Map을 용하여 코드를 개선해 보았다. js의 Map객체는 해시 테이블을 기반으로 하여 평균적으로 상수 시간 복잡도 O(1)에서 요소에 접근, 삽입, 삭제, 확인 등의 작업을 수행할 수 있다. (작업이 독립적으로 빠르게 수행될 수 있다는 것을 의미) 따라서 이중루프를 이용한 풀이보다 실행속도를 개선시킬 수 있었다.

 

//js 해시테이블일 이용해서 성능 개선
var twoSum2 = function(nums, target) {
    let map = new Map();
    for (let i = 0; i < nums.length; i++) {
        let gap = nums[i] - target;
        if (map.has(gap)) {
            return [map.get(gap), i];
        }
        map.set(nums[i], i);
    }
    return [];
};

 

 

만족스러운 실행속도가 나왔다.

최초 코드보다 두배정도 빨라졌다