ami-ryu/DailyAlgorithm

3 Sum

Closed this issue · 1 comments

ami-ryu commented

3 Sum | Problem

TwoSum 응용

1. Sort & 2-pointers

  • Space 절약할 수 있다는 장점이 있음

  • Time Complexity: O(n^2)

  • Space Complexity: O(logn) or O(n) --- depending on the implementation of the sorting algorithm.

/**
 * @param {number[]} nums
 * @return {number[][]}
 */

// Two Pointers - using TwoSum2
var threeSum1 = function(nums) {
  let res = [];
  nums.sort((a, b) => a - b);
  
  function twoSum2(i) {
    let lo = i + 1;
    let hi = nums.length - 1;
    
    while (lo < hi) {
      const sum = nums[i] + nums[lo] + nums[hi];
      if (sum < 0) lo++;
      else if (sum > 0) hi--;
      else {
        res.push([nums[i], nums[lo], nums[hi]]);
        lo++;
        hi--;
        while (lo < hi && nums[lo - 1] == nums[lo]) lo++;
      }
    }
  }
  
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > 0) break;
    if (i === 0 || nums[i-1] !== nums[i]) twoSum2(i);
  }
  
  return res;
};
  • 반복되는 중복 숫자는 건너뛰게하는 while문을 추가하여 시간복잡도 더욱 최적화하기
var threeSum = function(nums) {
  let res = [];
  nums.sort((a, b) => a - b);
  
  function twoSum2(i) {
    let lo = i + 1;
    let hi = nums.length - 1;
    
    while (lo < hi) {
      const sum = nums[i] + nums[lo] + nums[hi];
      if (sum < 0) {
        lo++;
        while (lo < hi && nums[lo - 1] == nums[lo]) lo++;
      } 
      else if (sum > 0) {
        hi--;
        while (lo < hi && nums[hi + 1] == nums[hi]) hi--;
      }
      else {
        res.push([nums[i], nums[lo], nums[hi]]);
        lo++;
        hi--;
        while (lo < hi && nums[lo - 1] == nums[lo]) lo++;
        while (lo < hi && nums[hi + 1] == nums[hi]) hi--;
      }
    }
  }
  
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > 0) break;
    if (i === 0 || nums[i-1] !== nums[i]) twoSum2(i);
  }
  
  return res;
};

2. Sort & HashMap

  • Time Complexity: O(n^2)
  • Space Complexity: O(n) --- hashmap
// Two Pointers - using TwoSum
var threeSum2 = function(nums) {
  nums.sort((a, b) => a - b);
  let res = [];
  
  function twoSum(i) {
    let seen = new Set();
    
    for (let j = i + 1; j < nums.length; j++) {
      const target = 0 - nums[i] - nums[j];
      if (seen.has(target)) {
        res.push([nums[i], nums[j], target]);
        while (nums[j] === nums[j+1]) j++;
      }
      seen.add(nums[j]);
    }
  }
  
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > 0) break;
    if (i === 0 || nums[i-1] !== nums[i]) twoSum(i);
  }
  
  return res;
}

// No Sort - using nested for loop
var threeSum = function(nums) {
  
  function isEqual(a, b) {
    
  }
}