[알고리즘] LeetCode - 3Sum

😳 영 좋지 않은 제목 3sum

물론 저 제목을 보고 이상한 걸 떠올리면 인성에 문제가 있다고 봐야...

Description

Given an array nums of n integers, are there elements, a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

n개의 정수로 이루어진 배열을 입력받아 세 요소의 합이 0이 되는 부분 집합을 반환하라.

Note

The solution set must not contain duplicate triplets.

부분집합은 unique 해야함.(중복되는거 있으면 안됨)

Example

nums = [-1, 0, 1, 2, -1, -4]

answer = [
  [-1, 0, 1],
  [-1, -1, 2],
]

도전!

중복되는 케이스를 피하려면 어떻게 해야하면 좋을까. 우선 잘 모르겠지만 걍 닥치고 정렬부터 해봄

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

두번째로 든 생각은 오름차순으로 정렬이 된 상태를 가정하면, 굳이 양수는 순회할 필요가 없다는 생각을 하게 됨

const firstPositive = nums.findIndex(num => num > 0);

만약 양수가 없다면? [0, 0, 0]이 아니면 답이 없다.

if (firstPositive === -1) {
  if (nums.filter(num => num ==== 0).length > 3) {
    return [[0, 0, 0]]
  }
  return []
}

이렇게 우선 허약한 녀석들을 먼저 해치웠다.

그다음 든 생각은 루프를 돌면서 숫자 하나를 택하고 해당 숫자의 index + 1부터 마지막 요소까지 양쪽에서 비교를 하면되지 않을까 생각함

-4(선택됨), -1(left), -1, 0, 1, 2(right)

for (let i = 0; i < firstPositive; i++) {
  const num = nums[i];
  let left = i + 1;
  let right = nums.length - 1;
  
  while (left < right) {
    const sum = num + nums[left] + nums[right];
    if (sum > 0) {
      right--
    } else if (sum < 0) {
      left++
    } else {
      answer.push([num, nums[left], nums[right]]);
    }
  }
}

이렇게만 하면 아마도 무한루프에 빠질듯 하다. 합이 0이 되는 경우에 left, right 인덱스를 어떻게 처리해주어야 할지 고민해봐야 한다.

먼저 든 생각은 걍 left++, right-- 해주면 되는거 아님? 이었으나, 다음 요소가 이전 요소와 같은 경우가 있으면 중복되는 조합을 리턴할 가능성이 있다. 그래서 다를 때 까지 인덱스를 늘리고 줄여줌.

left++;
right--;
while (left < right && nums[left] === nums[left - 1]) {
  left++;
}
while (left < right && nums[right] === nums[right + 1]) {
  right--;
}

그리고 또 하나 고려해야할 부분이 바깥 for문을 순회할 시에 현재 숫자가 이전 숫자와 같은 경우는 굳이 코드를 실행할 이유가 없다. 따라서...

if (i > 0 && nums[i] === nums[i - 1]) continue;

요렇게 한 줄 추가해 줌.
전체적인 코드는 아래와 같다.

var threeSum = function(nums) {
  nums.sort((a, b) => a - b) // sort nums array in ascending order
  const firstPositive = nums.findIndex((num) => num > 0) // find index of first positive number

  // if there is no positive number,
  // if nums array contains at least three zeros, then return [[0, 0, 0]],
  // or, there is no valid case
  if (firstPositive === -1) {
    if (nums.filter((num) => num === 0).length >= 3) {
      return [[0, 0, 0]]
    }
    return []
  }

  const answer = []

  // only iterate through the numbers less than or equal to zero
  for (let i = 0; i < firstPositive; i++) {
    // skip the number that is equal to the previous one
    if (i > 0 && nums[i] === nums[i - 1]) continue

    const num = nums[i]

    let left = i + 1
    let right = nums.length - 1

    // from both side of the rest elements, find the pair that makes zero.
    while (left < right) {
      const sum = num + nums[left] + nums[right]
      if (sum > 0) {
        right--
      } else if (sum < 0) {
        left++
      } else {
        answer.push([num, nums[left], nums[right]])
        left++
        right--
        while (nums[left] === nums[left - 1] && left < right) {
          left++
        }
        while (nums[right] === nums[right + 1] && left < right) {
          right--
        }
      }
    }
  }
  return answer
}

결과

Runtime: 128 ms, faster than 98.17% of JavaScript online submissions for 3Sum.
Memory Usage: 46.2 MB, less than 99.66% of JavaScript online submissions for 3Sum.