[LeetCode] 15. 3Sum

문제

LeetCode 15. 3Sum

https://leetcode.com/problems/3sum/

3Sum - LeetCode

언어

자바스크립트(JavaScript)

 

접근 방법

1. 중복 제거를 쉽게 하기 위해 오름차순으로 정렬한다.
2. 첫 번째 숫자를 고르면 두 수의 합 문제가 된다.
3. 처음 고르는 숫자 전에 같은 숫자가 있으면 중복이고, 두 번째 고르는 숫자 이후에 같은 숫자가 있으면 중복으로 간주한다.

코드

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let result = [];
    let sortedNums = nums.sort((a,b) => a-b);
    for (let i=0; i<sortedNums.length - 1; i++){
        // 처음으로 고르는 숫자전에 같은 숫자가 있으면 중복
        if(i !==0 && sortedNums[i] === sortedNums[i-1]){
            continue;
        }
        // 숫자 하나를 고르면 두 수의 합 문제
        let num1 = sortedNums[i];
        let map = new Map();
        let target1 = num1 * (-1);
        for (let j=i+1; j<sortedNums.length; j++){
            let num2 = sortedNums[j];
            let k = map.get(target1 - num2);
             // 두 번째로 고르는 숫자 이후에 같은 숫자가 있으면 중복
            if(sortedNums[j] === sortedNums[j+1]){
                map.set(num2, j);
                continue;
            }
            if ((k !== undefined) && (i !== j) && (j !== k) && (k !== i)){
                result.push([num1, num2, sortedNums[k]]); 
            }
            map.set(num2, j);
        }
    }
    return result;
};

결과

Runtime: 544 ms, faster than 26.11% of JavaScript online submissions for 3Sum.

Memory Usage: 49 MB, less than 58.54% of JavaScript online submissions for 3Sum.

복기

1. 힌트 없이 풀기 어렵다. 숫자를 하나 고르면 두 수의 합 문제가 되는지 떠올리기 어려웠다.
2. 시간 복잡도를 높이면 중복을 거르는 코드를 짜기가 쉬운데 O(n^2)로 풀어야 해서 어려웠다.