3Sum

15. 3Sum

문제 설명

정수 배열이 주어질 때, 3개의 엘리먼트가 i != j, i != k, j != k이고,
nums[i] + nums[j] + nums[k] === 0인 경우를 모두 찾으시오.

결과에 중복이 존재해서는 안된다.

해결 방법

투 포인터 탐색을 진행하기 위해 주어진 배열을 오름차순으로 정렬한다.

배열을 순회할 때, 인덱스 i를 기준으로 left = i + 1, right = nums.length - 1로 기준을 두고, 투 포인터 탐색을 진행한다.

1. 현재 세 숫자를 더한다.
2. 합이 0보다 작으면 left를 오른쪽으로 한 칸 옮긴다.
3. 합이 0보다 크면 right를 왼쪽으로 한 칸 옮긴다.
4. 0일 경우 결과에 저장하고, left와 right에 중복만큼 포인터를 넘긴다.

풀이 코드

export function threeSum(nums: number[]): number[][] {
  const result: number[][] = [];
  nums.sort((a, b) => a - b);

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

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

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];

      if (sum < 0) left++;
      else if (sum > 0) right--;
      else {
        result.push([nums[i], nums[left], nums[right]]);

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

  return result;
}

테스트 코드

import { describe, expect, test } from '@jest/globals';
import { threeSum } from '.';

describe(' description', () => {
  test('example test 1', () => {
    const output = threeSum([-1, 0, 1, 2, -1, -4]);
    const expected = [
      expect.arrayContaining([-1, -1, 2]),
      expect.arrayContaining([-1, 0, 1]),
    ];
    expect(output).toEqual(expected);
  });

  test('example test 2', () => {
    const output = threeSum([0, 1, 1]);
    const expected = [];

    expect(output).toEqual(expected);
  });

  test('example test 3', () => {
    const output = threeSum([0, 0, 0]);
    const expected = [[0, 0, 0]];
    expect(output).toEqual(expected);
  });
});