3Sum - Two Pointer Algorithm

3Sum - LeetCode

문제

리스트에서 세개의 숫자를 합쳐서 0이 되는 모든 조합을 반환하라.

단, 결과가 겹쳐서는 안된다.

---

문제 해결 방안

숫자 하나를 잡고 나머지 숫자들을 two pointer로 조합을 찾아낸다.

목표 합보다 두 포인터의 합이 더 크면 right 포인터를 낮추고,
두 포인터의 합이 더 작으면 left 포인터를 높인다.

---

코드 (TypeScript)

function threeSum(nums: number[]): number[][] {
    let result: [number, number, number][] = [];
    
    // sort nums increasing
    nums.sort((a, b) => a - b);
    
    let i = 0;
    
    while (i < nums.length - 2) {
        // two pointer algorithm
        let left = i + 1;
        let right = nums.length - 1;
        let sum = -nums[i];
        
        while (left < right) {
            // find result
            if (nums[left] + nums[right] == sum) {
                // add answer into result list
                result.push([nums[i], nums[left], nums[right]]);
                
                // skip left duplicates
                while (left < right && nums[left] == nums[left + 1]) {
                    left++;
                }
                
                // skip right duplicates
                while (left < right && nums[right] == nums[right - 1]) {
                    right--;
                }
                
                // move pointer
                left++;
                right--;
            } else if (nums[left] + nums[right] < sum) {
                left++;
            } else {
                right--;
            }
        }
        
        // skip i duplicates
        for (; i < nums.length - 2; i++) {
            if (nums[i] !== nums[i + 1]) {
                break;
            }
        }
        
        i++;
    }
    
    return result;
};