09. 세 수의 합(leetcode: 15)

3Sum - LeetCodeLeetCode

문제링크

문제 분석

숫자의 배열이 주어졌을 때 세 수의 합이 0이 되는 값들을 배열로 묶어서 리턴하는 문제. 0이 되는 묶음이 여러개 존재할 수 있다.

값의 합이나 뺄셈을 통해서 특정한 값을 찾을 때는 정렬을 이용해서 푸는게 가장 쉬운 방법이다. 따라서 이 문제도 주어진 배열을 정렬을 하자.

이후에는 투포인터을 조금 응용해서 포인터 하나를 시작점에 두고 left, right 포인터로 범위를 줄여 나가면서 문제를 풀이하면 된다.

풀이

var threeSum = function(nums) {
  let ret = [];
  // 정렬. 오름차순으로 정렬하자 화살표함수의 내용물이 한줄이면 평가된 값이 그대로 리턴된다.
  nums.sort((a, b) => a - b);
  // 정답의 조건은 세 수의 배열이므로 3개의 수가 되지 않는 크기면 바로 종료
  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) {
      let sum = nums[i] + nums[left] + nums[right]
      // 포인터의 간격을 줄이는 조건은 sum의 값에 따라서.
      // 이게 가능한 이유는 앞서서 정렬을 했기 때문
      if (sum > 0) {
        right -= 1;
      } else if (sum < 0) {
        left += 1;
      } else {
        ret.push([nums[i], nums[left], nums[right]]);
        // 여기서도 중복된 값 제거
        while (left < right && nums[left] == nums[left + 1]) {
          left += 1;
        }
        while (left < right && nums[right] == nums[right - 1]) {
          right -= 1;
        }
        left += 1;
        right -= 1;
      }
    }
  }
  return ret;  
};