[LeetCode] 18. 4Sum

3Sum 문제의 코드와 크게 다르지 않게 해결이 가능하다.

투포인터를 사용하되, 확인해야하는 값이 4개이므로 1번째와 2번째 요소는 반복을 통해 찾도록 한다.

이후 3번째와 4번째 인자를 투포인터를 활용하여 빠르게 탐색한다.

😎풀이

function fourSum(nums: number[], target: number): number[][] {
    // 결과를 저장할 배열
    const result = [];
    
    // 입력 배열의 길이
    const n = nums.length;
    
    // 입력 배열을 오름차순으로 정렬
    nums.sort((a, b) => a - b);
    
    // 첫 번째 숫자를 선택 (i)
    for (let i = 0; i < n - 3; i++) {
        // 중복된 첫 번째 숫자는 건너뜀
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        
        // 두 번째 숫자를 선택 (j)
        for (let j = i + 1; j < n - 2; j++) {
            // 중복된 두 번째 숫자는 건너뜀
            if (j > i + 1 && nums[j] === nums[j - 1]) continue;
            
            // 남은 두 숫자를 찾기 위해 투 포인터 사용
            let left = j + 1;
            let right = n - 1;
            
            while (left < right) {
                const sum = nums[i] + nums[j] + nums[left] + nums[right];
                
                if (sum === target) {
                    // 타겟과 일치하는 조합을 찾았을 때 결과에 추가
                    result.push([nums[i], nums[j], nums[left], nums[right]]);
                    
                    // 중복된 세 번째 숫자는 건너뜀
                    while (left < right && nums[left] === nums[left + 1]) left++;
                    // 중복된 네 번째 숫자는 건너뜀
                    while (left < right && nums[right] === nums[right - 1]) right--;
                    
                    // 포인터 이동
                    left++;
                    right--;
                } else if (sum < target) {
                    // 합이 타겟보다 작으면 left 포인터를 오른쪽으로 이동
                    left++;
                } else {
                    // 합이 타겟보다 크면 right 포인터를 왼쪽으로 이동
                    right--;
                }
            }
        }
    }
    
    return result;
}