[leetcode, JS] 15. 3Sum

문제

문제 링크 : 3Sum

풀이

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const result = [], n = nums.length;
    nums.sort()

    const set = new Set();

    for(let i=0; i<n; i++) {
        const map = new Map();

        for(let j=i+1; j<n; j++){
            if( map.has(-nums[i]-nums[j]) && !set.has(`${[nums[i],-nums[i]-nums[j],nums[j]]}`)) {
                result.push([nums[i],-nums[i]-nums[j],nums[j]]);
                set.add(`${[nums[i],-nums[i]-nums[j],nums[j]]}`);
            }

            map.set(nums[j])
        }
    }

    return result;

};

1. Map과 Set을 이용한 풀이를 참고
2. nums 배열을 sort 하고
3. -nums[i]-nums[j] 값이 map에 있는지, set에 중복되지 않는지 체크하여 result에 push

• Runtime 2380 ms, Memory 81.7 MB
• 런타임과 메모리 효율성 극악

다른 풀이

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    nums.sort((a, b) => a - b);

    let ans = [];
    
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) break;

        let target = -nums[i];
        let _lp = i + 1, _rp = nums.length - 1;
        while (_lp < _rp) {
            if (nums[i] > 0) break;

            let sum = nums[_lp] + nums[_rp];
            if (sum === target) {
                ans.push([nums[i], nums[_lp], nums[_rp]]);
                while (nums[_lp + 1] === nums[_lp]) _lp++;
                _lp++;
            } else if (sum < target) {
                _lp++;
            } else _rp--;
        }

        while (nums[i + 1] === nums[i]) i++;
    }

    return ans;
};

1. 배열 nums를 for문을 돌리는데, for문 안에서 -num[i]를 target을 구하는 while문을 돌리니 num[i]가 0보다 클 때는 break;
2. 위에서 말한 것처럼, target이 lp,rp의 sum과 같으면 push
3. 나머지 조건들은 lp++이거나 rp--

• Runtime 152 ms, Memory 58 MB