15. 3Sum

💡 풀이

// O(N*N)
var threeSum = function (nums) {
  nums.sort((a, b) => a - b);

  let answer = [];

  for (let i = 0; i < nums.length; i++) {
    if (i === 0 || (i > 0 && nums[i] !== nums[i - 1])) {
      let low = i + 1;
      let high = nums.length - 1;
      let sum = 0 - nums[i];

	  // 중요 부분
      while (low < high) {
        if (nums[low] + nums[high] === sum) {
          answer.push([nums[i], nums[low], nums[high]]);
          
          // 중복 스킵
          while (low < high && nums[low] === nums[low + 1]) low++;
          while (low < high && nums[high] === nums[high - 1]) high--;
          
          low++;
          high--;
        } else if (nums[low] + nums[high] < sum) {
          // 중복 스킵
          while (low < high && nums[low] === nums[low + 1]) low++;
          low++;
        } else {
          // 중복 스킵
          while (low < high && nums[high] === nums[high - 1]) high--;
          high--;
        }
      }
    }
  }
  console.log('answer: ', answer);
  return answer;
};

let nums = [-1, 0, 1, 2, -1, -4];
threeSum(nums);

📝 정리

참고할 문제: Two Sum

이번 문제는 스스로 못 풀었고, 스터디원분의 도움을 받아서 풀었다. 푸는 방식 자체는 two Sum 문제와 유사하지만, pointer 3개를 사용한다는 점과 중복을 허용하지 않는다는 점(가장 고생했던 부분이다..)이 다른 점이라고 볼 수 있겠다!

위의 '중요 부분' 이라고 주석이 적혀있는데, 해당 부분 아래로는 two Sum을 풀었던 방식과 매우 유사하다. 다만, sum이 0-nums[i]가 되어 있는데, 최초의 sum(=== -1 * nums[i])과 나머지 두 수를 더하면 0(=target값)이 나와야 하는데 그래서 0에서 i 포인터가 지나가는 부분의 요소를 빼준 것이다.

추가적으로, 중복에 관한 부분은 while문 안의 while문에서 중복을 발견한다면 (nums[low] === nums[low+1]) low의 인덱스를 1씩 증가시키도록, 즉 중복을 스킵하도록 하였다. (high도 마찬가지다.)

수정, 지적을 환영합니다!

문제 링크

https://leetcode.com/problems/3sum/

LeetCode GitHub

https://github.com/tTab1204/LeetCode