Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Notice that the solution set must not contain duplicate triplets.
Constraints
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
Approach
Links
GeeksforGeeks
ProgramCreek
YouTube
Examples
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Input: nums = [0]
Output: []
Input: nums = []
Output: []
Solutions
/**
* Time complexity :
* Space complexity :
*/
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> resultList = new HashSet();
if(nums == null || nums.length < 3) {
new ArrayList(resultList);
}
helper(nums, resultList, new LinkedList<Integer>(), 0, 0);
return new ArrayList(resultList);
}
private void helper(int[] nums,
Set<List<Integer>> resultList,
LinkedList<Integer> currList,
int start,
int sum) {
if(currList.size() == 3) {
if(sum == 0) {
List<Integer> tmpList = new ArrayList(currList);
Collections.sort(tmpList);
resultList.add(tmpList);
}
return;
}
for(int i = start; i < nums.length; i++) {
currList.add(nums[i]);
helper(nums, resultList, currList, i+1, sum+nums[i]);
currList.removeLast();
}
}
}
/**
* Time complexity :
* Space complexity :
*/
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> res = new HashSet<>();
int n = nums.length;
Arrays.sort(nums);
for(int i = 0; i < n; i++) {
int val = nums[i];
int l = i+1;
int r = n-1;
while(l < r) {
int sum = val + nums[l] + nums[r];
if(sum == 0) {
res.add(Arrays.asList(val, nums[l++], nums[r--]));
}
else if(sum < 0) l++;
else if(sum > 0) r--;
}
}
return new ArrayList<>(res);
}
}
/**
* Time complexity :
* Space complexity :
*/
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0; i < nums.length; i++) {
if(nums[i] > 0) break;
if(i > 0 && nums[i-1] == nums[i]) continue;
int l = i+1, r = nums.length-1;
while(l < r) {
int sum = nums[i] + nums[l] + nums[r];
if(sum < 0) l++;
else if(sum > 0) r--;
else {
res.add(Arrays.asList(nums[i], nums[l], nums[r]));
while(l < r && nums[l] == nums[l+1]) l++;
while(l < r && nums[r] == nums[r-1]) r--;
l++;
r--;
}
}
}
return res;
}
}