LeetCode 15 - 3Sum (Medium)

 

💡 문제

LeetCode - 15번

 

🎯 풀이 과정

주어진 배열에서 3개의 원소의 조합 중 합이 0인 것들을 중복없이 모두 찾는 문제입니다.

다만 입력 크기를 고려해서 일반 조합 알고리즘보다 효율적인 방법이 필요합니다.

 

투 포인터 알고리즘을 활용하면, 특정 합 S 를 만족하는 배열 쌍을 중복없이 찾는데 활용할 수 있습니다.

이때 배열은 정렬이 된 상태여야합니다. (중복 제거를 위해)

 

이 문제를 약간 변형해보면 세 원소 중 가장 첫번째 요소를 pivot 으로 정하고,

나머지 두 요소는 pivot 을 제외한 구간에서 sum - arr[pivot] 을 찾는 문제로 해석할 수 있습니다.

이때 중복 제거를 위해 pivot 이 바로 직전 pivot 값과 동일할 경우 무시하고,

마찬가지로 나머지 두 요소 중 첫번째 요소인 head 를 정할 때 이전 head 와 동일하다면 무시해줍니다.

 

👨‍💻 코드

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    function twoSum(pivot) {
        const result = []

        let head = pivot + 1
        let tail = nums.length - 1

        while (head < tail) {
            const sum = nums[pivot] + nums[head] + nums[tail]

            if (sum === 0) {
                if (head > pivot + 1 && nums[head] === nums[head - 1]) {
                    head += 1
                    continue
                }

                result.push([nums[pivot], nums[head], nums[tail]])
                head += 1
            } else if (sum < 0) {
                head += 1
            } else {
                tail -= 1
            }
        }

        return result
    } 

    const answer = []

    nums.sort((a, b) => a - b)

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

        const result = twoSum(pivot)

        answer.push(...result)
    }   

    return answer
};