🤖 leetcode 15. 3Sum | medium | two-pointer | javascript

🗒️ Problems

3Sum - LeetCode

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

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.

two sum에 이은 three sum 문제.

✨ Idea

• nums 에서 하나의 숫자(value)를 선택하고, 중복을 피하기 위해서 이후 오른쪽 나머지 array 에서 twoSum을 이용해서 앞의 선택된 -value 를 찾는다.
• twoSum 문제는 sorted array에서 two pointers 기법으로 찾는다.
• 중복되는 숫자에 대한 처리가 어려웠는데, labuladong의 좋은 책에 좋은 방법이 나와서 정리해봅니다.

🍀 Intuition

숫자 하나 ([object Object]) 선택 후 twoSum 으로 [object Object] 값 찾기

• twoSum 을 left-right two pointers 기법 사용하기 위하여 nums 정렬.

nums.sort((a, b) => a - b);

for (let i = 0; i < N; i += 1) {
  const cur = nums[i];

  twoSum(i + 1, N - 1, -cur);
}

sorted array에서 left-right two pointers 이용한 two sum

Two Sum II - Input Array Is Sorted - LeetCode

nums.sort((a,b) => a - b);
...
    const twoSum = (left, right, target) => {
        while (left < right) {
            const sum = nums[left] + nums[right];

            if (sum > target) {
                right -= 1;
            } else if (sum < target) {
                left += 1;
            } else if (sum === target) {
                return [ left, right ] ;
            }
        }
    }
    return [ -1, -1]

💡 일반화된 two sum 의 left-right two pointers 기법

중복된 값의 경우에는 skip 하도록 처리 추가함.

  leftValue       rightValue
    |                 |
... 2  2   ...    3   3
    |                 |
   left ->        <- right

• left 포인터의 값이 바뀔때까지 계속 증가

while (left < right && nums[left] === leftValue) left += 1;

• right 포인터의 값이 바뀔때까지 계속 감속

while (left < right && nums[right] === rightValue) right -= 1;

const twoSum = (left, right, target) => {
  while (left < right) {
    const leftValue = nums[left];
    const rightValue = nums[right];

    const sum = leftValue + rightValue;

    if (sum > target) {
      while (left < right && nums[right] === rightValue) right -= 1;
    } else if (sum < target) {
      while (left < right && nums[left] === leftValue) left += 1;
    } else if (sum === target) {
      res.push([-target, nums[left], nums[right]]);
      while (left < right && nums[right] === rightValue) right -= 1;
      while (left < right && nums[left] === leftValue) left += 1;
    }
  }
};

💡 최초 값 선택 시에도 중복 처리 처리 추가

앞에서 선택한 값이 동일한 경우에는 skip 처리 추가

for (let i = 0; i < N; i += 1) {
  const cur = nums[i];

  twoSum(i + 1, N - 1, -cur);

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

🔥 My Solution

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

  nums.sort((a, b) => a - b);

  const res = [];

  const twoSum = (left, right, target) => {
    while (left < right) {
      const leftValue = nums[left];
      const rightValue = nums[right];

      const sum = leftValue + rightValue;

      if (sum > target) {
        while (left < right && nums[right] === rightValue) right -= 1;
      } else if (sum < target) {
        while (left < right && nums[left] === leftValue) left += 1;
      } else if (sum === target) {
        res.push([-target, nums[left], nums[right]]);
        while (left < right && nums[right] === rightValue) right -= 1;
        while (left < right && nums[left] === leftValue) left += 1;
      }
    }
  };

  for (let i = 0; i < N; i += 1) {
    const cur = nums[i];

    twoSum(i + 1, N - 1, -cur);

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

  return res;
};