def fourSum(nums, target):
nums.sort()
quadruplets = []
n = len(nums)
for i in range(n - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
left = j + 1
right = n - 1
while left < right:
total = nums[i] + nums[j] + nums[left] + nums[right]
if total == target:
quadruplets.append([nums[i], nums[j], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif total < target:
left += 1
else:
right -= 1
return quadruplets
nums = [1, 0, -1, 0, -2, 2]
target = 0
print(fourSum(nums, target))
Explanation:
The "4Sum" problem asks to find all unique quadruplets in the array whose sum is equal to the target.
The Python, Java, and C++ solutions follow a similar approach:
Sort the array in ascending order.
Iterate over the array, fixing the first two elements of the potential quadruplet (nums[i] and nums[j]).
Use two pointers, left and right, to find the other two elements.
Calculate the current sum as nums[i] + nums[j] + nums[left] + nums[right].
If the current sum is equal to the target, add the quadruplet to the result list. Move both left and right pointers while skipping duplicates.
If the current sum is less than the target, increment the left pointer to increase the sum.
If the current sum is greater than the target, decrement the right pointer to decrease the sum.
Skip duplicates by comparing the current element with the previous one.
Repeat the above steps for all elements in the array.
Return the list of quadruplets found.
The time complexity of the solution is O(n^3), where n is the number of elements in the array.
I hope this explanation helps! Let me know if you have any further questions.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List> quadruplets = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int left = j + 1;
int right = n - 1;
while (left < right) {
int total = nums[i] + nums[j] + nums[left] + nums[right];
if (total == target) {
quadruplets.add(Arrays.asList(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 (total < target) {
left++;
} else {
right--;
}
}
}
}
return quadruplets;
}
public static void main(String[] args) {
int[] nums = {1, 0, -1, 0, -2, 2};
int target = 0;
Solution solution = new Solution();
System.out.println(solution.fourSum(nums, target));
}
}
Explanation:
The "4Sum" problem asks to find all unique quadruplets in the array whose sum is equal to the target.
The Python, Java, and C++ solutions follow a similar approach:
Sort the array in ascending order.
Iterate over the array, fixing the first two elements of the potential quadruplet (nums[i] and nums[j]).
Use two pointers, left and right, to find the other two elements.
Calculate the current sum as nums[i] + nums[j] + nums[left] + nums[right].
If the current sum is equal to the target, add the quadruplet to the result list. Move both left and right pointers while skipping duplicates.
If the current sum is less than the target, increment the left pointer to increase the sum.
If the current sum is greater than the target, decrement the right pointer to decrease the sum.
Skip duplicates by comparing the current element with the previous one.
Repeat the above steps for all elements in the array.
Return the list of quadruplets found.
The time complexity of the solution is O(n^3), where n is the number of elements in the array.
I hope this explanation helps! Let me know if you have any further questions.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector> fourSum(vector& nums, int target) {
sort(nums.begin(), nums.end());
vector> quadruplets;
int n = nums.size();
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int left = j + 1;
int right = n - 1;
while (left < right) {
int total = nums[i] + nums[j] + nums[left] + nums[right];
if (total == target) {
quadruplets.push_back({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 (total < target) {
left++;
} else {
right--;
}
}
}
}
return quadruplets;
}
int main() {
vector nums = {1, 0, -1, 0, -2, 2};
int target = 0;
vector> result = fourSum(nums, target);
for (const auto& quadruplet : result) {
for (const int& num : quadruplet) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
Explanation:
The "4Sum" problem asks to find all unique quadruplets in the array whose sum is equal to the target.
The Python, Java, and C++ solutions follow a similar approach:
Sort the array in ascending order.
Iterate over the array, fixing the first two elements of the potential quadruplet (nums[i] and nums[j]).
Use two pointers, left and right, to find the other two elements.
Calculate the current sum as nums[i] + nums[j] + nums[left] + nums[right].
If the current sum is equal to the target, add the quadruplet to the result list. Move both left and right pointers while skipping duplicates.
If the current sum is less than the target, increment the left pointer to increase the sum.
If the current sum is greater than the target, decrement the right pointer to decrease the sum.
Skip duplicates by comparing the current element with the previous one.
Repeat the above steps for all elements in the array.
Return the list of quadruplets found.
The time complexity of the solution is O(n^3), where n is the number of elements in the array.
I hope this explanation helps! Let me know if you have any further questions.