LeetCode No.15 - 3Sum

카테고리: Algorithms

January 17, 2022

문제링크

접근

우선 주어진 배열 nums를 오름차순으로 정렬한 후, 기준이 되는 i 포인터를 잡아서 정수 3개의 합을 구하는 문제를 2개의 합을 구하는 문제로 바꿉니다. i 포인터를 기준으로 하는 left와 right 포인터를 움직여서, nums[i], nums[left], nums[right] 세 수의 합을 구하는 방식으로 접근하였습니다:

15번 문제 접근 방식
15번 문제 접근 방식

그러다 세 수의 합이 0보다 작으면 left 포인터를 오른쪽으로, 반대로 0보다 크면 right 포인터를 왼쪽으로 옮겨가면서 탐색해나갑니다.

만약 세 수의 합이 0인 경우, 즉 정답을 찾은 경우엔 두 포인터를 동시에 옮겨야하는데 이때 정답엔 중복된 세 쌍(triplet)이 나오면 안되므로 현재 left, right 포인터가 가리키고 있는 값과 포인터가 이동했을 때 가리키게 되는 다음값이 같지 않게될 때까지 while문을 돌려서 중복을 방지합니다.

자바스크립트 구현

function threeSum(nums) {
  const { length } = nums;
  const answer = [];
  nums.sort((a, b) => a - b);
  
  for (let i = 0; i < length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;  
    let [left, right] = [i + 1, length - 1];
    
    while (left < right) {
      const sumCandidate = nums[i] + nums[left] + nums[right];
      
      if (sumCandidate === 0) {
        answer.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--;
      } 
      else if (sumCandidate < 0) left++;
      else right--;
    }
  }
  
  return answer;
}