[LeetCode] 15. 3Sum 풀이 (JS)

0. 문제

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

3Sum - LeetCode

숫자로 이루어진 배열이 주어 질 때, 합이 0이 되는 세개의 원소를 배열로 리턴

#1
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

#2
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

#3
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

1.언어

자바스크립트(JavaScript)

 

2. 문제 풀이

2-1 중첩 포문으로 모든 경우 수 검사

var threeSum = function(nums) {
    let res=[], arr = new Map(), str = new Map();
   
    arr.set(nums[0],true)
    
    
    for (let i=1; i<nums.length-1; i++){
        for (let j=i+1; j<nums.length; j++){
            let val = (nums[i] + nums[j]) * -1;
            if (arr.get(val)){
                val = [nums[i],nums[j],val].sort((x,y) => x-y)
                if (!str.get(String(val))){
                    str.set(String(val),true)
                    res.push(val);
                }
            }
        }
        arr.set(nums[i],true)
    }
    return res
};

Runtime: 6333 ms, faster than 5.00% of JavaScript online submissions for 3Sum.

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

 

2-2 투 포인터 접근

const threeSum = (nums) => {
  const answer = [];
  const N = nums.length;

  nums.sort((a, b) => a-b);
    
  for (let standard=0; standard < N-2; standard++) {
    let left = standard+1;
    let right = N-1;
    
     if(nums[standard] === nums[standard-1]) continue;

      
    while (left < right) {
      const total = nums[standard] + nums[left] + nums[right]
      if (total === 0) {

        answer.push([nums[standard], nums[left], nums[right]]);
        while (left < right && nums[left] === nums[left+1]) left++;
        while (left < right && nums[right] === nums[right-1]) right--;

        left++;
        right--;

      } else if (total > 0) {
        right--;
      } else {
        left++;
      }
    }
  }
  return answer
}

Runtime: 155 ms, faster than 88.71% of JavaScript online submissions for 3Sum.

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

 

첫 번째 작성한 코드는 결과를 보니 비효율적인 걸 느껴 검색 중 투 포인터 알고리즘을 공부했다.

투 포인터로 이중 반복문으로 처리해야할 문제를 반복문 하나로 처리 가능하게 하여 시간복잡도가 줄었다.

 

 

투 포인터 알고리즘

https://velog.io/@wken5577/%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0Two-Pointer-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

투 포인터(Two Pointer) 알고리즘