15. 3Sum

문제링크: https://leetcode.com/problems/3sum/

Solution

1. Brute force

가장 기본적인 반복문 3번을 이용한 O(n^3) 해법이다. 중복된 값들을 제거하기 위해 Set을 사용했다.

var threeSum = function(nums) {
  // Brute force
  const myMap = new Map();
  // don't count 3 more same num
  const newNums = [];
  for (let num of nums) {
    if (!myMap.has(num)) {
      myMap.set(num, 1);
      newNums.push(num);
    } else {
      const count = myMap.get(num);
      if (count < 3) {
        myMap.set(num, count + 1);
        newNums.push(num);
      }
    }
  }
  
  const mySet = new Set();
  for (let i = 0; i < newNums.length - 2; i++) {
    for (let j = i + 1; j < newNums.length - 1; j++) {
      const sum2 = newNums[i] + newNums[j];
      for (let k = j + 1; k < newNums.length; k++) {
        if (-sum2 === newNums[k]) mySet.add([newNums[i], newNums[j], newNums[k]].sort().join());
      }
    }
  }
  return result = Array.from(mySet).map((el) => el.split(',').map((el2) => parseInt(el2)));

};

2. Sort & binary search

두 개의 값을 반복해서 지정하고 마지막 값은 이진 탐색을 통해 찾는 방법이다.
O(n^2logn)의 시간 복잡도가 필요하다.

var threeSum = function(nums) {
  // if Brute force > O(nlogn) sort생각해보기
  // With sort (n^2logn)
  // 1. sort만 하기 2. 3중복 제거하기
  const myMap = new Map();
  const filteredNums = [];
  // let zeroCount = 0;
  // num count
  for (let num of nums) {
    if (!myMap.has(num)) {
      myMap.set(num, 1);
      filteredNums.push(num);
    } else {
      const count = myMap.get(num);
      if (count < 3) {
        myMap.set(num, count + 1);
        filteredNums.push(num);
      }
    }
  }
  
  // filter maximum 3 nums
  filteredNums.sort((a,b) => a - b);
  // console.log(filteredNums);
  
  // Select 2 and Binary search
  const result = new Set();
  for (let i = 0; i < filteredNums.length - 2; i++) {
    for (let j = i + 1; j < filteredNums.length - 1; j++) {
      if (filteredNums[i] + filteredNums[j] + filteredNums[j + 1] > 0) break;
      // BS
      const target = -filteredNums[i] - filteredNums[j];
      let left = j + 1;
      let right = filteredNums.length - 1;
      while (left <= right) {
        // console.log(target,left, right);
        const mid = parseInt((left + right) / 2);
        if (filteredNums[mid] === target) {
          const curResult = `${filteredNums[i]},${filteredNums[j]},${target}`
          result.add(curResult);
          break;
        } else {
          filteredNums[mid] < target ? left = mid + 1 : right = mid - 1;
        }
      }
    }
  }
  // console.log(result);
  return Array.from(result).map((el) => el.split(',').map((el2) => parseInt(el2)))

};

3. Sort & 2 pointers

하나의 값은 순서대로 지정하고 나머지 값은 2Sum과 같이 2 pointer를 이용해 찾는다.

Algorithm

• nums 배열을 오름차순 정렬한다.
• 반복을 통해 숫자 하나를 선택한다, 동일한 숫자가 연속해서 두 번 지정되지 않도록 한다.
• 2Sum과 같이 목표값을 2 pointer로 찾는다. 합이 크면 왼쪽 index를 키우고 작으면 오른쪽 index를 줄인다.
• 목표값을 찾으면 결과를 저장하고 다음 유효값도 찾는다.

var threeSum = function (nums) {
	// 오름차순 정렬
  nums.sort((a, b) => a - b);
  let output = [], i = 0;
  while (i < nums.length - 2) {
    let l = i + 1, r = nums.length - 1;
    while (l < r) {
      if (nums[l] + nums[r] + nums[i] == 0) {
        output.push([nums[i], nums[l], nums[r]]);
        // 같은 값은 패스
        while (nums[l] == nums[l + 1]) {
            l++;
        };
        l++
      } else if (nums[l] + nums[r] + nums[i] > 0) {
        r--;
      } else {
        l++;
      };
    };
    // 같은 값은 패스
    while (nums[i] === nums[i + 1]) {
      i++;
    };
    i++;
  };
  return output;
};