📌 문제 설명

3Sum 문제 보기

📌 문제 접근

문제 이해

하나를 기준 잡고 투 포인터로 하면 되는 간단한 문제. 보통 O(N^3)으로 풀이하면 시간초과가 나므로, 정렬 후 O(N^2)으로 풀이해야 한다.

중복 잡기

여기서 문제는 중복을 찾는 것. 처음에 고민했다가, 먼저 같은 기준 원소를 건너뛰는 로직을 추가했다. 하지만, 포인터가 가르키는 값도 중복될 수 있으므로, 그 부분도 처리해야 했다. 따라서 0이 될 때만 while문으로 중복을 건너뛰는 로직을 추가했다.

최적화 한스푼

마지막으로 정렬된 상태이므로, 기준 원소가 양수면 더 이상 탐색할 필요가 없다.

📌 내가 작성한 코드

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const threeSum = (nums) => {
    nums.sort((a,b) => a - b);
    const answer = [];
    
    for (let i = 0; i < nums.length - 2; i++){
        if(nums[i] > 0) break;
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        
        let [left, right] = [i + 1, nums.length - 1];
        const now = nums[i];
        
        while(left < right){
            const sum = now + nums[left] + nums[right];
            
            if (sum === 0){
                answer.push([now, nums[left++], nums[right--]]);
                while (left < right && nums[left] === nums[left - 1]) left++;
                while (left < right && nums[right] === nums[right + 1]) right--;
            }
            else if (sum > 0) right--;
            else left++;
        }
    }
    return answer;
};

📌 시간 복잡도

O(N^2) - 정렬 후 각 기준 원소마다 left/right 포인터가 배열을 한 번씩만 이동합니다.

📌 참고 링크

• MDN Array.prototype.sort()

• Two Pointers Technique - GeeksforGeeks