[Reet code] 18. 4Sum

Intuition

이전에 푼 n개 합 문제 시리즈 중 하나다. 방법은 이전 문제들과 완전히 동일하다.

Approach

정렬 후 맨 앞 두개를 고정한 후 lower, upper bound 를 좁혀나간다.

Complexity

• Time complexity: O(N^3)
  k 개 합 문제의 복잡도는 O(N^(k-1)) 이 된다.

Code

function fourSum(nums: number[], target: number): number[][] {
    const result: number[][] = []
    nums.sort((a, b) => a - b)
    for(let i =0; i<nums.length - 3; i ++) {
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue
        }
        for(let j =i+1; j< nums.length - 2; j ++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) {
                continue
            }
            let left = j + 1
            let right = nums.length - 1
            const twoSum = nums[i] + nums[j]
            while (left < right) {
                const temp = twoSum + nums[left] + nums[right]
                if ( temp < target ) {
                    left ++
                } else if (temp === target) {
                    result.push([nums[i], nums[j], nums[left], nums[right]])
                    while(nums[left] === nums[left + 1]) left++;
                    while(nums[right] === nums[right - 1]) right--;
                    left ++
                    right--
                } else {
                    right--
                }
            }
        }
    }
    return result
};