4Sum
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that 0 <= a, b, c, d < n, a, b, c, and d are distinct, and nums[a] + nums[b] + nums[c] + nums[d] == target.
Sample Input
nums = [1,0,-1,0,-2,2], target = 0
Sample Output
[[-2,-1,1,2],[-2,0,0,2],[-1,0,1,1]]
Constraints
- 1 <= nums.length <= 200
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
Test Cases
Case 1
Args: [[1,0,-1,0,-2,2],0]
Expected: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Topics
Sort the array. Use two nested loops to fix the first two numbers, then use two pointers to find the remaining two. Skip duplicates at every level to avoid duplicate quadruplets.
function fourSum(nums, target) {
nums.sort((a, b) => a - b);
const result = [];
const n = nums.length;
for (let i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
for (let j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] === nums[j - 1]) continue;
let left = j + 1, 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++;
else right--;
}
}
}
return result;
}
Time: O(n³) Space: O(1) (ignoring output)
Saved in this browser only. Private to you.