[75 LeetCode] 1 - TwoSum

[75 LeetCode]는 코딩테스트 연습을 위해 한 페이스북 개발자가 추천하는 75가지 알고리즘 문제를 풀어보는 시리즈이다.

블라인드 원문:
https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU

 

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

Two Sum - LeetCode

TwoSum

우선 가장 단순한 풀이법을 생각했다.

nums의 각 숫자마다 뒤의 목록을 순회하며 더했을 때 target이 되는 값을 찾는다.

function twoSum(nums: number[], target: number): number[] {
    for (let i = 0; i<nums.length - 1; i++ ) {
        let a = nums[i];
        for (let j = i + 1; j < nums.length; j++) {
            let b = nums[j];

            if (a + b === target) {
                return [i, j];
            }
        }
    }
};

시간 복잡도: O(n^2)
공간 복잡도: O(1)

통과는 했으나, 더 좋은 방법이 있다고 힌트가 나오고 있었다.

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

시간 복잡도의 차수를 내리는 방법이 있을것이라고 추론했다.
공간 복잡도가 O(1)이니, 메모리를 추가로 사용해서 처음 순회 시 알 수 있는 정보를 저장해둘 수 있을 것 같다고 생각했다.

우리가 필요한 정보는 특정값의 인덱스이다. (a + b = target에서 b = target - a의 인덱스)
즉, indexMap을 만들어 순회 시 { [num]: index }를 저장해두면, a가 주어질 때 target-b값이 Map에 있는지만 찾으면 된다.

한 아이템을 중복사용할 수 없다는 제약이 있기 때문에 a의 index와 target-b의 인덱스가 달라야 함을 체크해줬다.

function twoSum(nums: number[], target: number): number[] {
    const indexMap: Record<number, number> = {};

    nums.forEach((num, i) => indexMap[num] = i);

    for (let i = 0; i < nums.length - 1; i++ ) {
        let a = nums[i];
        let operand = target - a;

        let targetIndex = indexMap[operand];

        if (!targetIndex || targetIndex === i) {
            continue;
        } 
        if (targetIndex) {
            return [i, targetIndex];
        }
    }
};

단순히 초기화단계 -> 순회 단계로 돌렸다.

시간복잡도: O(n) 
공간복잡도: O(n)

풀고나서 풀이를 보니, 초기화 단계가 없어도 됐다.
순회 하면서 순회된 아이템을 Map에 집어넣는 방식이다.

function twoSum(nums: number[], target: number): number[] {
    const indexMap: Record<number, number> = {};
    let a, operand, targetIndex;

    for (let i = 0; i < nums.length; i++ ) {
        a = nums[i];
        operand = target - a;

        if (operand in indexMap) {
            return [i, indexMap[operand]];
        }

        indexMap[a] = i;
    }
};