[LeetCode] 1 Two Sum JavaScript

문제 링크

Two Sum - LeetCode

 

문제 유형

배열, Hash Map

 

문제 풀이

해당 문제는 숫자 배열과 target 값이 주어지고 배열 내 임의의 두 숫자를 더하면 target 값이 되는 두 숫자의 인덱스를 배열 형태로 출력하는 문제이다. 이 문제는 해시 테이블을 이용하면 O(n)의 시간복잡도로 문제를 해결할 수 있다.

먼저, 해시 테이블 Map을 생성하고, 배열을 순차적으로 접근한다. 만약 현재 숫자가 해시 테이블에 저장되어 있지 않다면 target 값에서 현재 숫자를 뺀 값을 저장한다. 이때, target 값에서 현재 숫자를 뺀 값은 더해지는 나머지 숫자가 된다. 만약 현재 숫자가 해시 테이블에 저장되어 있다면 해시 테이블에서 현재 숫자를 키로 갖는 값과 현재 인덱스를 출력한다.

 

코드

var twoSum = function(nums, target) {
    // Hash Map
    const map = new Map();
    const answer = new Array(2).fill(0);
    for (let i = 0; i < nums.length; i++) {
        if (!map.has(nums[i])) {
            map.set(target - nums[i], i);
        } else {
            answer[0] = map.get(nums[i]);
            answer[1] = i;
            break;
        }
    }
    return answer;
};

 

참고

https://www.youtube.com/watch?v=y-0DZ1MFN1g