Description:
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 < na,b,c, anddare distinct.nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Examples:
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]Solution in Python:
To solve the problem of finding all unique quadruplets in an array that sum up to a given target, we can use a combination of sorting and the two-pointer technique. This approach is efficient for this kind of problem, which is a variant of the well-known “4-sum” problem.
Python
from typing import List
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
# Sort the array to facilitate the two-pointer technique
nums.sort()
# Initialize the result list
result = []
# Length of the array
n = len(nums)
# Loop through each element, considering it as the first element of the quadruplet
for i in range(n):
# Skip duplicate elements to avoid duplicate quadruplets
if i > 0 and nums[i] == nums[i-1]:
continue
# Loop through each element after the first element, considering it as the second element of the quadruplet
for j in range(i + 1, n):
# Skip duplicate elements to avoid duplicate quadruplets
if j > i + 1 and nums[j] == nums[j-1]:
continue
# Initialize two pointers
left, right = j + 1, n - 1
# Use the two-pointer technique to find the remaining two elements
while left < right:
# Calculate the sum of the current quadruplet
total = nums[i] + nums[j] + nums[left] + nums[right]
# If the sum equals the target, add the quadruplet to the result list
if total == target:
result.append([nums[i], nums[j], nums[left], nums[right]])
# Move the left pointer to the right, skipping duplicates
while left < right and nums[left] == nums[left + 1]:
left += 1
left += 1
# Move the right pointer to the left, skipping duplicates
while left < right and nums[right] == nums[right - 1]:
right -= 1
right -= 1
# If the sum is less than the target, move the left pointer to the right
elif total < target:
left += 1
# If the sum is greater than the target, move the right pointer to the left
else:
right -= 1
return resultExplanation:
- Sorting the Array:
- We sort the array to simplify the process of finding quadruplets and to use the two-pointer technique effectively.
- Loop through Each Element for the First and Second Elements of the Quadruplet:
- We use two nested loops to fix the first (
i) and second (j) elements of the quadruplet. - We skip duplicate elements to avoid adding duplicate quadruplets to the result list.
- We use two nested loops to fix the first (
- Two-pointer Technique for the Remaining Two Elements:
- We initialize two pointers:
left(right after the second element) andright(at the end of the array). - We then move these pointers to find the remaining two elements such that their sum with the first two elements equals the target.
- We initialize two pointers:
- Handling Different Cases:
- If the sum of the quadruplet equals the target, we add it to the result list and adjust the pointers to skip duplicates.
- If the sum is less than the target, we move the left pointer to the right to increase the sum.
- If the sum is greater than the target, we move the right pointer to the left to decrease the sum.
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, target) {
// Sort the array to facilitate the two-pointer technique
nums.sort((a, b) => a - b);
// Resultant array to store the quadruplets
const result = [];
// Length of the array
const n = nums.length;
// Loop through each element to consider it as the first element of the quadruplet
for (let i = 0; i < n; i++) {
// Skip duplicate elements to avoid duplicate quadruplets
if (i > 0 && nums[i] === nums[i - 1]) continue;
// Loop through each element after the first element to consider it as the second element of the quadruplet
for (let j = i + 1; j < n; j++) {
// Skip duplicate elements to avoid duplicate quadruplets
if (j > i + 1 && nums[j] === nums[j - 1]) continue;
// Initialize two pointers
let left = j + 1;
let right = n - 1;
// Use the two-pointer technique to find the remaining two elements
while (left < right) {
// Calculate the sum of the current quadruplet
const total = nums[i] + nums[j] + nums[left] + nums[right];
// If the sum equals the target, add the quadruplet to the result array
if (total === target) {
result.push([nums[i], nums[j], nums[left], nums[right]]);
// Move the left pointer to the right, skipping duplicates
while (left < right && nums[left] === nums[left + 1]) left++;
left++;
// Move the right pointer to the left, skipping duplicates
while (left < right && nums[right] === nums[right - 1]) right--;
right--;
}
// If the sum is less than the target, move the left pointer to the right
else if (total < target) {
left++;
}
// If the sum is greater than the target, move the right pointer to the left
else {
right--;
}
}
}
}
return result;
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
// Sort the array to facilitate the two-pointer technique
Arrays.sort(nums);
// Resultant list to store the quadruplets
List<List<Integer>> result = new ArrayList<>();
// Length of the array
int n = nums.length;
// Loop through each element to consider it as the first element of the quadruplet
for (int i = 0; i < n; i++) {
// Skip duplicate elements to avoid duplicate quadruplets
if (i > 0 && nums[i] == nums[i - 1]) continue;
// Loop through each element after the first element to consider it as the second element of the quadruplet
for (int j = i + 1; j < n; j++) {
// Skip duplicate elements to avoid duplicate quadruplets
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
// Initialize two pointers
int left = j + 1;
int right = n - 1;
// Use the two-pointer technique to find the remaining two elements
while (left < right) {
// Calculate the sum of the current quadruplet
int total = nums[i] + nums[j] + nums[left] + nums[right];
// If the sum equals the target, add the quadruplet to the result list
if (total == target) {
result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
// Move the left pointer to the right, skipping duplicates
while (left < right && nums[left] == nums[left + 1]) left++;
left++;
// Move the right pointer to the left, skipping duplicates
while (left < right && nums[right] == nums[right - 1]) right--;
right--;
}
// If the sum is less than the target, move the left pointer to the right
else if (total < target) {
left++;
}
// If the sum is greater than the target, move the right pointer to the left
else {
right--;
}
}
}
}
return result;
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> FourSum(int[] nums, int target) {
// Sort the array to facilitate the two-pointer technique
Array.Sort(nums);
// Resultant list to store the quadruplets
IList<IList<int>> result = new List<IList<int>>();
// Length of the array
int n = nums.Length;
// Loop through each element to consider it as the first element of the quadruplet
for (int i = 0; i < n; i++) {
// Skip duplicate elements to avoid duplicate quadruplets
if (i > 0 && nums[i] == nums[i - 1]) continue;
// Loop through each element after the first element to consider it as the second element of the quadruplet
for (int j = i + 1; j < n; j++) {
// Skip duplicate elements to avoid duplicate quadruplets
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
// Initialize two pointers
int left = j + 1;
int right = n - 1;
// Use the two-pointer technique to find the remaining two elements
while (left < right) {
// Calculate the sum of the current quadruplet
int total = nums[i] + nums[j] + nums[left] + nums[right];
// If the sum equals the target, add the quadruplet to the result list
if (total == target) {
result.Add(new List<int> { nums[i], nums[j], nums[left], nums[right] });
// Move the left pointer to the right, skipping duplicates
while (left < right && nums[left] == nums[left + 1]) left++;
left++;
// Move the right pointer to the left, skipping duplicates
while (left < right && nums[right] == nums[right - 1]) right--;
right--;
}
// If the sum is less than the target, move the left pointer to the right
else if (total < target) {
left++;
}
// If the sum is greater than the target, move the right pointer to the left
else {
right--;
}
}
}
}
return result;
}
}