Skip to content

Three sum problem #2741

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 4 commits into from
Oct 28, 2021
Merged

Three sum problem #2741

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
4 commits
Select commit Hold shift + click to select a range
1169fca
Added Two Sum Problem
Sneha421 Oct 11, 2021
3dd5d38
Added ThreeSumProblem
Sneha421 Oct 26, 2021
ff84064
Merge branch 'master' into ThreeSumProblem
Sneha421 Oct 26, 2021
80b6f2c
Merge branch 'master' into ThreeSumProblem
siriak Oct 28, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
109 changes: 109 additions & 0 deletions Misc/ThreeSumProblem.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,109 @@
import java.util.*;
public class ThreeSumProblem {
public static void main(String args[])
{
Scanner scan = new Scanner(System.in);
System.out.print("Enter the target sum ");
int ts= scan.nextInt();
System.out.print("Enter the number of elements in the array ");
int n = scan.nextInt();
System.out.println("Enter all your array elements:");
int arr[]= new int[n];
for(int i=0;i<n;i++)
{
arr[i]=scan.nextInt();
}
ThreeSumProblem th = new ThreeSumProblem();
System.out.println("Brute Force Approach\n"+(th.BruteForce(arr,ts))+"\n");
System.out.println("Two Pointer Approach\n"+(th.TwoPointer(arr,ts))+"\n");
System.out.println("Hashmap Approach\n"+(th.Hashmap(arr,ts)));

}
public List<List<Integer>> BruteForce(int[] nums,int target) {
List<List<Integer>> arr = new ArrayList<List<Integer>>();

for(int i=0;i<nums.length;i++)
{
for(int j=i+1;j<nums.length;j++)
{
for(int k=j+1;k<nums.length;k++)
{
if(nums[i]+nums[j]+nums[k]==target)
{ List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(nums[j]);
temp.add(nums[k]);
Collections.sort(temp);
arr.add(temp);
}


}
}
}
arr = new ArrayList<List<Integer>>(new LinkedHashSet<List<Integer>>(arr));
return arr;
}
public List<List<Integer>> TwoPointer(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> arr = new ArrayList<List<Integer>>();
int start=0;
int end=0;
int i = 0;
while(i<nums.length-1)
{
start=i+1;
end=nums.length-1;
while (start<end)
{
if (nums[start]+nums[end]+nums[i]==target)
{
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(nums[start]);
temp.add(nums[end]);
arr.add(temp);
start++;
end--;
}
else if (nums[start]+nums[end]+nums[i]<target)
start+=1;
else
end-=1;

}
i++;
}
Set<List<Integer>> set = new LinkedHashSet<List<Integer>>(arr);
return new ArrayList<List<Integer>>(set);
}
public List<List<Integer>> Hashmap(int[] nums, int target) {
Arrays.sort(nums);
Set<List<Integer>> ts = new HashSet();
HashMap<Integer,Integer> hm = new HashMap<>();

for(int i=0;i<nums.length;i++)
{
hm.put(nums[i],i);
}

for(int i=0;i<nums.length;i++)
{
for(int j=i+1;j<nums.length;j++)
{
int t= target - nums[i] - nums[j];
if(hm.containsKey(t) && hm.get(t)>j)
{
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(nums[j]);
temp.add(t);
ts.add(temp);
}
}
}
return new ArrayList(ts);
}

}

1 change: 0 additions & 1 deletion Misc/TwoSumProblem.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,5 +1,4 @@
package Misc;

import java.util.*;
import java.util.stream.Collectors;

Expand Down