[Leetcode / Javascript] 15. 3Sum

문제는 다음과 같습니다.

숫자의 배열이 주어지고 배열의 원소 중 3개를 더해서 0이 만들어지는 조합을 찾는 문제입니다.

문제 해결방법은 다음과 같습니다.

nums 배열을 정렬한 후 제일 앞 원소를 조합의 첫 번째 숫자로 지정합니다. 그리고 그 뒤에 있는 숫자들 중 조건을 만족하는 나머지 2개의 숫자를 찾습니다. nums 배열을 순회하면서 이 과정을 반복합니다. 

즉, 3개의 숫자 중 가장 작은 수를 하나 뽑고 나머지 숫자의 조합을 찾는 방법입니다. nums 배열이 정렬되어 있기 때문에 첫 번째 숫자가 0보다 크다면 합이 0이 될 수 없기 때문에 순회를 종료합니다.

나머지 숫자에서 2개를 찾는 방법은 다음과 같습니다.

첫 번째 숫자 바로 다음 숫자의 index를 lo로 지정하고 가장 마지막 index를 hi로 지정합니다. 그리고 첫 번째 숫자, nums[lo], nums[hi]의 합에 따라 lo와 hi의 값을 적절히 변경합니다. 세 숫자의 합은 세 가지 경우로 나뉩니다.

• sum > 0 : sum을 줄여야하기 때문에 hi--를 합니다
• sum < 0 : sum을 늘려야하기 때문에 lo++를 합니다
• sum == 0 : 조합을 찾았으므로 lo++, hi--를 합니다.

 

sum의 값에 따라 lo와 hi 값을 변경할 수 있는 이유는 nums 배열이 정렬되어있기 때문입니다. nums[lo] <= nums[lo + 1] 와 nums[hi] >= nums[hi - 1] 가 항상 참이기 때문입니다.

코드를 보겠습니다.

function threeSum(_nums: number[]): number[][] {
  const answer: number[][] = [];
  const nums = _nums.sort((a, b) => a - b);
  if (nums.length < 3) return answer;      // 1

  for (let i = 0; i < nums.length - 2; i++) {
    if (nums[i] > 0) return answer;        // 2
    if (nums[i] === nums[i - 1]) continue; // 3

    let lo = i + 1;
    let hi = nums.length - 1;

    while (lo < hi) {
      const sum = nums[i] + nums[lo] + nums[hi];

      if (sum === 0) {
        answer.push([nums[i], nums[lo], nums[hi]]);
        while (lo < hi && nums[lo] === nums[lo + 1]) lo++;  // 4
        while (lo < hi && nums[hi] === nums[hi - 1]) hi--;  // 5
        lo++;
        hi--;
        continue;
      }

      if (sum > 0) {
        while (lo < hi && nums[hi] === nums[hi - 1]) hi--;
        hi--;
        continue;
      }

      while (lo < hi && nums[lo] === nums[lo + 1]) lo++;
      lo++;
    }
  }

  return answer;
}

console.log(threeSum([-1, 0, 1, 2, -1, -4]));   // [[-1, -1, 2], [-1, 0, 1]]

추가적인 설명입니다.

1. nums.length가 3보다 작으면 조건을 만족시키지 못하기 때문에 []을 바로 리턴합니다.
2. 첫 번째 숫자인 nums[i]가 양수면 합이 0이 될 수 없기 때문에 answer를 바로 리턴합니다.
3. 같은 계산이 반복되는 것을 피하기 위해 첫 번째 숫자가 이전 값과 같으면 넘어갑니다.
4. 같은 계산이 반복되는 것을 피하기 위해 증가한 lo가 이전 값과 다를 때까지 계속 증가시킵니다.
5. 같은 계산이 반복되는 것을 피하기 위해 감소한 hi가 이전 값과 다를 때까지 계속 감소시킵니다.