이전에 푼 n개 합 문제 시리즈 중 하나다. 방법은 이전 문제들과 완전히 동일하다.
정렬 후 맨 앞 두개를 고정한 후 lower, upper bound 를 좁혀나간다.
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
};