Dare2Solve
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.
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:
left
just after the current element and right
at the end of the array.left
pointer, and the element at the right
pointer.right
pointer left to reduce the sum.left
pointer right to increase the sum.Return the Result:
After iterating through the array, return the result list containing all unique triplets.
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).
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.
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
set<vector<int>> uniqueTriplets;
vector<vector<int>> 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;
}};
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
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
Set<List<Integer>> uniqueTriplets = new HashSet<>();
List<List<Integer>> 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;}}
var threeSum = function(nums) {
nums.sort((a, b) => a - b);
let st= new Set ();
for (i=0;i<nums.length;i++){
let left = i+1;
let right = nums.length-1;
let sum =0;
while (left < right ){
sum = nums[i]+nums[left]+nums[right];
if (sum==0){
st.add(JSON.stringify([nums[i],nums[left],nums[right]]))
left ++;
right--;}
else if(sum > 0 )
right--;
else {
left++;
}}}
return Array.from(st).map((el)=>JSON.parse(el))
};