[leetcode][TS] 1. Two Sum

문제

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

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

 

예시

코드

// O(n²)
function twoSum(nums: number[], target: number): number[] {
    
    for(let i = 0; i < nums.length; i++){
        const num = target - nums[i];
        const index = nums.indexOf(num);
        
        if(index !== -1 && index !== i){
            // 배열에 있으면서 자기 자신이 아닐 때
            return [i, index];
        }
    }
};

// O(n)
function twoSum(nums: number[], target: number): number[] {
    // key : num, value : index
    const map = new Map();
    
    for(let i = 0; i < nums.length; i++){
        const num = target - nums[i];
        
        if(map.get(num)!==undefined){
            return [i, map.get(num)]
        }
        
        map.set(nums[i], i);
    }
};

처음에는 `indexOf`를 활용해 풀었는데, 시간 복잡도를 줄이기 위해 `Map`을 활용하여 다시 풀었다.

map의 key는 nums의 요소들이고, value는 각 요소의 인덱스를 저장하였다. `nums 요소 + 다른 nums 요소 = target`을 다른 말로 쓰면, `nums 요소 = target - 다른 nums 요소` 가 된다. 따라서 map에 target에서 현재 nums 요소를 뺀 값이 있다면 더해서 target을 만들 수 있는 값이 있다는 의미이므로 각 인덱스를 리턴하였고, 없다면 map에 해당 nums 요소의 값과 인덱스를 추가해주었다.

 

 

`indexOf`의 경우, 인자로 위치를 찾고 싶은 요소를 넣어주는데 이때 앞에서부터 순차적으로 확인하기 때문에 `O(n)`의 시간복잡도를 가진다. 따라서 for문과 함께 써주게 되면 시간 복잡도가 `O(n²)`이 된다.

`Map`의 경우 (V8 엔진 기준) 해시 테이블로 구현되어 있다. 따라서 대부분 `Map`에서의 조회는 `O(1)`의 시간 복잡도를 가진다. 대부분이라고 한 이유는, 해시 테이블이 특정 기준에 따라 꽉 차있으면 재해싱 되는데, `set()` 이나 `delete()` 작업 중 재해싱이 일어난다. 재해싱은 해시 테이블의 크기를 늘리고, 기존 키의 해시 값을 재계산해서 새 테이블에 다시 삽입하는 과정을 거친다. 이때, 데이터를 재배치하는 과정에서 기존 테이블의 모든 요소에 대해서 처리하기 때문에 `O(n)`의 시간 복잡도를 가지게 된다. 그러나, 재해싱 되는 경우는 드물기 때문에 `O(1)`의 시간 복잡도를 보통 가진다고 설명한다.