Problem:
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
Java Solution
This problem can be solved by using two pointers. Time complexity is O(n^2).
To avoid duplicate, we can take advantage of sorted arrays, i.e., move pointers by >1 to use same element only once.
public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); ArrayList<List<Integer>> result = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { int j = i + 1; int k = nums.length - 1; if (i > 0 && nums[i] == nums[i - 1]) { continue; } while (j < k) { if (k < nums.length - 1 && nums[k] == nums[k + 1]) { k--; continue; } if (nums[i] + nums[j] + nums[k] > 0) { k--; } else if (nums[i] + nums[j] + nums[k] < 0) { j++; } else { ArrayList<Integer> l = new ArrayList<>(); l.add(nums[i]); l.add(nums[j]); l.add(nums[k]); result.add(l); j++; k--; } } } return result; } |
Duplicates can be removed using the sets in the cpp ! Is there anyone who can help me with the solution using the sets in cpp to remove the duplicates
Great explanation. Thank you.
This problem is explained in an easy to understand and detailed article on Code Recipe as well that explains the both brute force and efficient solution in depth. They have explained solution in Java, Golang and Python. Leaving link for others to refer: https://www.code-recipe.com/post/three-sum
aa
The above solution wont work with the following
Input: [-2,0,0,2,2]
Output: [[-2,0,2],[-2,0,2]]
Expected: [[-2,0,2]]
Duplicates can be handled using HashSet also.
class Solution {
public List<List> threeSum(int[] nums) {
Set<List> result = new HashSet();
if(nums == null || nums.length<3)
return new ArrayList();
Arrays.sort(nums);
for(int i=0; i<nums.length-2; i++){
int j=i+1;
int k=nums.length-1;
while(j<k){
if(nums[i]+nums[j]+nums[k]==0){
List l = new ArrayList();
l.add(nums[i]);
l.add(nums[j]);
l.add(nums[k]);
result.add(l);
j++;
k–;
}else if(nums[i]+nums[j]+nums[k]<0){
j++;
}else{
k–;
}
}
}
return new ArrayList(result);
}
}
Nice article.
avoiding duplicates
if(i==0 || nums[i] > nums[i-1])
why do you need this condition? isn’t it always true for sorted array?
Thanks for the solution, it’s really helpful. This article http://bit.ly/29YmZI4 also has a in-depth analysis of 3sum question with variations.
Not the best or fasted but cleaner and easier to understand
public static List<List> threeSum(int[] nums) {
List<List> result = new ArrayList<List>();
if(nums == null || nums.length == 0) {
return result;
}
Arrays.sort(nums);
Map tripMap = new HashMap();
dumpArray(nums);
for(int i = 0; i < nums.length - 2; i++){
int j = i + 1;
int k = nums.length - 1;
while ( j < k) {
if(nums[i] + nums[j] + nums[k] == 0){
List trip = new ArrayList(Arrays.asList(new Integer[]{nums[i], nums[j] , nums[k]}));
String tripKey = nums[i] + "" + nums[j] + "" + nums[k];
if(!tripMap.containsKey(tripKey)) {
result.add(trip);
tripMap.put(tripKey, true);
}
j++;
k--;
}else if(nums[i] + nums[j] + nums[k] < 0) {
j++;
} else {
k--;
}
}
}
return result;
}
public static boolean is3SumArray(int [] arr1, int sum1){
Arrays.sort(arr1);
for(int i=0; i<arr1.length-2; i++)
{
int left = i+1;
int right = arr1.length-1;
while(left<right)
{
int result = arr1[i] + arr1[left] + arr1[right];
if(result==sum1)
return true;
else if(resultsum1)
right–;
}
}
return false;
}
The method below has any error? Or it just becauses that the complexity is n^3 ,so it cannot pass the leetcode.
public class Solution {
public List<List> threeSum(int[] nums) {
List<List> result = new ArrayList<List>();
List list = new ArrayList();
if(nums == null || nums.length == 0){
return result;
}
Arrays.sort(nums);
dfs(result, list, nums, 0, 0);
return result;
}
private void dfs(List<List> result, List list, int[] nums, int cur, int sum){
if(list.size() == 3 && sum == 0){
result.add(new ArrayList(list));
return;
}
if(list.size() > 3 || cur >= nums.length){
return;
}
for(int i=cur; icur && nums[i]==nums[i-1])
// continue;
list.add(nums[i]);
dfs(result, list, nums, i+1, sum+nums[i]);
list.remove(list.size()-1);
}
}
}
Here’s my accepted solution.
Reviews are welcome: https://github.com/mgireesh05/leetcode/blob/master/3sum/src/com/mgireesh/Solution.java
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class Solution {
public List<List> threeSum(int[] nums) {
List<List> answer = new LinkedList<List>();
if (nums.length < 3) {
return answer;
}
Arrays.sort(nums);
int find = 0;
int prev_i = nums[0] - 1;
for (int i = 0; i < nums.length - 2; i++) {
if ((prev_i != nums[0] - 1) && (nums[i] == prev_i)) {
continue;
}
prev_i = nums[i];
int prev_j = nums[0] - 1;
for (int j = i + 1; j j; k--) {
if ((prev_k != nums[0] - 1) && (find == prev_k)) {
continue;
}
if (nums[k] == find) {
List solSet = new LinkedList();
solSet.add(nums[i]);
solSet.add(nums[j]);
solSet.add(nums[k]);
answer.add(solSet);
prev_k = find;
} else if (find > nums[k]) {
break;
}
}
}
}
return answer;
}
}
This solution still giving duplicate triplets. Following changes would make this solution complete I guess to avoid duplicates.
in case2, also add while loop for start++, same as in case 1
in case 3, also add while loop for end–, same as in case 1.
and finally at the end, inside for loop, add following while loop for avoiding duplicate negate values.
while(i < a.length-1 && a[i+1] == -negate) {
i++;
}
private static ArrayList<ArrayList> threeSum(int []S, int target)
{
ArrayList<ArrayList> list = new ArrayList<ArrayList>();
Arrays.sort(S);
for(int i=0;i<S.length;i++)
{
for(int j=i+1;j<S.length;j++)
{
for(int k=j+1;k<S.length;k++)
{
if((S[i]+S[j]+S[k]) == target)
{
ArrayList result = new ArrayList();
result.add(S[i]);
result.add(S[j]);
result.add(S[k]);
list.add(result);
}
}
}
}
return list;
}
The better solution may have a duplicate result. If input is [0, 0, 0, 0], output will be [[0,0,0], [0,0,0]]
To avoid it, before add to result, we should check if the temp ArrayList is already in the result.
Can someone plz explain why my code is getting timed out:
public static List<List> threeSum(int[] nums) {
Set<List> res = new HashSet<List>();
Arrays.sort(nums);
for(int i=1; i=0 && ki && j<nums.length){
int sumG = nums[k] + nums[j];
if(sumG + nums[i] == 0){
List list = new ArrayList();
list.add(nums[k]);
list.add(nums[i]);
list.add(nums[j]);
res.add(list);
k–; j++;
}
else if(sumG + nums[i] > 0){
k–;
}
else{
j++;
}
}
}
return new ArrayList(res);
}
my solution complexity n*n
HashMap map = new HashMap();
int[] a = new int[] {4,5,6,7,8,-10};
// Arrays.sort(a);
for(int j=0;j<a.length;j++){
int suma = -1*a[j];
for(int i=j;i<a.length;i++){
if(i!=j){
int b = suma-a[i];
if(map.containsKey(a[i])==false){
map.put(b,a[i]);
}else{
Integer g = (Integer) map.get(a[i]);
System.out.println(a[i]+"+"+g+"+"+-1*suma+"=0");
}
}
}
map.clear();
}
Hi ryanlr,
Can you please correct my below prog that I wrote using PK’s algo & your 2Sum code using HashMap? I think I didn’t get the algorithm properly. Thank you.
public List<List> threeSum(int[] nums) {
List<List> result = new ArrayList<List>();
HashSet<List> hSet = new HashSet<List>();
if(nums.length < 3)
return result;
HashMap hMap = new HashMap();
for(int i=0; i<nums.length; i++) {
int target = -nums[i];
if(hMap.containsKey(nums[i])) {
List temp = new ArrayList();
temp.add(nums[i]);
temp.add(nums[hMap.get(nums[i])]);
temp.add(-target);
if(!hSet.contains(temp)) {
hSet.add(temp);
result.add(temp);
}
}
else
hMap.put(target – nums[i], i);
}
return result;
}
Hello, I have a problem. I don’t understand how avoid duplicate solutions using ”
if (i == 0 || num[i] > num[i – 1]) {“
It will give time limit exceeded in O(n^2) solution…
A lot of code can be avoided by using a class Triplet {} and adding it to a set
It looks working, but time is n^3.
A great idea! Here is how to use hashmap to solve 2Sum problem: http://www.programcreek.com/2012/12/leetcode-solution-of-two-sum-in-java/
Pseudocode :
Iterate the array num[].
Int target = -num[i];
Now find twoSum for above target in array num using hashmap.
int a[] = {2, 7, 11, 0, 9, 15, 7};
for(int i = 0; i<a.length; i++){
for(int j = i+1; j<a.length; j++){
for(int k = j+1; k<a.length; k++){
if(a[i]+a[j]+a[k] == 9){
System.out.println(i + " and "+ j + " and " + k);
}
}
}
}
int a[] = {2, 7, 11, 0, 9, 15, 7};
for(int i = 0; i<a.length; i++){
for(int j = i+1; j<a.length; j++){
for(int k = j+1; k<a.length; k++){
if(a[i]+a[j]+a[k] == 9){
System.out.println(i + " and "+ j + " and " + k);
}
}
}
}
If first condition is true then second condition will not be evaluated
my solution
int[] array = {-1, 0, 1, 2, -1, -4, 2,-1,-1};
int current = array[0];
for (int i = 0; i < array.length; i++) {
for (int j = i; j <= 2 + i && i+2 < array.length -1 ; j++) {
if (current + array[j] + array[j + 1] == 0) {
System.out.println(current + " " + array[j] + " " + array[j + 1]);
}
current = array[i];
}
}
if (i == 0 || num[i] > num[i – 1]) {
How does this execute for i = 0 case ? , wont you be trying to evaluate num[-1] ??
okay in last iteration we have only two element left so we should come out from the loop…
I got it !!!
why are you running only num.length-2 times.
Make some changes to solution1 and accepted!!
public class Solution {
public static ArrayList<ArrayList> threeSum(int[] num) {
//sort array
Arrays.sort(num);
ArrayList<ArrayList> result = new ArrayList<ArrayList>();
for(int i=0; i 0) break;
for(int j=i+1; j 0 && num[j] > 0) break;
for(int k=j+1; k<num.length; k++){
if(num[i] + num[j] + num[k] == 0) {
ArrayList each = new ArrayList();
each.add(num[i]);
each.add(num[j]);
each.add(num[k]);
result.add(each);
}
while (1+k<num.length && num[k]==num[k+1]) k++;
}
while (j+1<num.length && num[j]==num[j+1]) j++;
}
while (i+1<num.length && num[i]==num[i+1]) i++;
}
return result;
}
}
Your solution is wrong. You did not eliminate the duplicated combinations.
same complexity
Seems, I have a better solutions of this problem
boolean is3SumArray(int[] a) {
if (a.length < 3) return false;
Arrays.sort(a);
for (int i = 0; i < a.length-2; i++) {
int x = a[i];
int yI = i+1;
int zI = a.length-1;
while (yI 0) zI–;
else yI++;
}
}
return false;
}