[LeetCode] 1. Two Sum (JS)

https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

핵심 아이디어

• value: index HashMap을 만들어서 pair(target - num)의 index를 1회당 O(1)에 찾기
• 배열 탐색과 동시에 hash map 초기

 

복잡도

• 시간 복잡도: O(n)
  • 1차원 배열 탐색, hashMap 초기화 O(n) * hashMap get O(1)
• 공간 복잡도: O(n)
  • 1차원 hashMap O(n)

 

설명

주어진 배열에서 합이 target이 되는 두 숫자의 index를 찾는 문제이다. 단순하게 brute force로 이중 for문을 이용하여 모든 합의 경우의 수를 검사해 본다면 O(n^2)의 시간이 걸린다. 그러나, 숫자 하나가 정해졌을 때 짝이 되는 숫자의 값은 target - num으로 정해져 있으므로 {value: index} 형태의 hash map을 구성하고, hashMap.get(target - num) 을 이용해 짝이 되는 index를 한 번에 O(1)의 시간으로 구할 수 있다. hashMap initialize를 배열 탐색에 앞서 하지 않고, 배열 탐색을 하며 동시에 쌓아가는 방식으로 구현하면 2n이 걸릴 시간을 n으로 추가로 줄일 수 있다. 이렇게 구현하면 시간 복잡도는 1차원 배열을 한번 탐색하는 시간 O(n) * 1회당 hashMap에서 get 하는 시간 O(n)으로 O(n)의 시간 복잡도로 문제를 해결할 수 있다.

 

코드 (Javascript)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const indexMap = new Map(); // num: index
    
    for( [idx, num] of nums.entries()) {
        const pairIdx = indexMap.get(target - num);
        
        if(pairIdx !== undefined && pairIdx !== idx) {
            return [pairIdx, idx];
        }
        
        indexMap.set(num, idx);
    }
};

 

유튜브 NeetCode 해설 영상