🎨Now live: Try our Free AI Image Generation Feature

Intuition
The problem requires finding all unique triplets in the array that sum up to zero. The key observation is that sorting the array helps in efficiently finding these triplets using a two-pointer approach. Sorting ensures that we can avoid duplicates easily and systematically move towards the solution.
Approach
- Sort the Array:
Sort the input array
nums
in non-decreasing order. This helps in handling duplicates and efficiently using the two-pointer technique. - Iterate Through the Array:
Use a for loop to iterate through the array:
- For each element, set it as the first element of the triplet.
- Initialize two pointers:
left
just after the current element andright
at the end of the array. - Use a while loop to move the pointers towards each other: - Calculate the sum of the three elements: the current element, the element at theleft
pointer, and the element at theright
pointer. - If the sum is zero, add the triplet to the result list and move both pointers inward, skipping duplicate elements. - If the sum is greater than zero, move theright
pointer left to reduce the sum. - If the sum is less than zero, move theleft
pointer right to increase the sum. - Skip duplicate elements for the current element to avoid duplicate triplets. - Return the Result: After iterating through the array, return the result list containing all unique triplets.
Complexity
Time Complexity:
O(n^2), where n
is the length of the array. Sorting the array takes O(n log n), and the two-pointer technique for each element takes O(n), resulting in an overall time complexity of O(n^2).
Space Complexity:
O(n), as the result list stores all the unique triplets. Sorting the array in-place uses O(1) additional space, and the set used for avoiding duplicates is not needed since the array is sorted.
Code
C++
#include
#include
#include
using namespace std;
class Solution {
public:
vector> threeSum(vector& nums) {
sort(nums.begin(), nums.end());
set> uniqueTriplets;
vector> result;
for (int i = 0; i < nums.size(); ++i) {
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
uniqueTriplets.insert({nums[i], nums[left], nums[right]});
++left;
--right;
} else if (sum > 0) {
--right;
} else {
++left;}}}
for (const auto& triplet : uniqueTriplets) {
result.push_back(triplet);
}
return result;
}};
Python
from typing import List
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
unique_triplets = set()
result = []
for i in range(len(nums)):
left, right = i + 1, len(nums) - 1
while left < right:
sum = nums[i] + nums[left] + nums[right]
if sum == 0:
unique_triplets.add((nums[i], nums[left], nums[right]))
left += 1
right -= 1
elif sum > 0:
right -= 1
else:
left += 1
for triplet in unique_triplets:
result.append(list(triplet))
return result
Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
class Solution {
public List> threeSum(int[] nums) {
Arrays.sort(nums);
Set> uniqueTriplets = new HashSet<>();
List> result = new ArrayList<>();
for (int i = 0; i < nums.length; ++i) {
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
uniqueTriplets.add(Arrays.asList(nums[i], nums[left], nums[right]));
++left;
--right;
} else if (sum > 0) {
--right;
} else {
++left;
}}}
result.addAll(uniqueTriplets);
return result;}}
JavaScript
var threeSum = function(nums) {
nums.sort((a, b) => a - b);
let st= new Set ();
for (i=0;i 0 )
right--;
else {
left++;
}}}
return Array.from(st).map((el)=>JSON.parse(el))
};