/**
* Given an array of integers(+ve,-ve,0 or duplicates). Find n print all triplets such that a+b+c=0.
* e.g. Let A = -1 0 9 5 -5 2 3
* Answer = {0 5 -5} {-5 2 3}.
* Expected : Time O(n2) Space O(1)
*/
public class Prob3Sum {
public void find3Sum(int A[]){
for(int i=0; i<A.length; i++){
int l = i+1;
int r = A.length - 1;
while(l<r){
if(A[i] + A[l] + A[r] == 0){
System.out.println("Sum: " + A[i] + " " + A[l] + " " + A[r]);
}
if(A[i] + A[l] + A[r] > 0)
r--;
else
l++;
}
}
}
public static void main(String args[]){
QuickSort sort = new QuickSort();
sort.A = new int[]{-1, 0, 9, 5, -5, 2, 3};
sort.quickSort(sort.A, 0, sort.A.length-1);
sort.printArr();
Prob3Sum ps = new Prob3Sum();
ps.find3Sum(sort.A);
}
}
* Given an array of integers(+ve,-ve,0 or duplicates). Find n print all triplets such that a+b+c=0.
* e.g. Let A = -1 0 9 5 -5 2 3
* Answer = {0 5 -5} {-5 2 3}.
* Expected : Time O(n2) Space O(1)
*/
public class Prob3Sum {
public void find3Sum(int A[]){
for(int i=0; i<A.length; i++){
int l = i+1;
int r = A.length - 1;
while(l<r){
if(A[i] + A[l] + A[r] == 0){
System.out.println("Sum: " + A[i] + " " + A[l] + " " + A[r]);
}
if(A[i] + A[l] + A[r] > 0)
r--;
else
l++;
}
}
}
public static void main(String args[]){
QuickSort sort = new QuickSort();
sort.A = new int[]{-1, 0, 9, 5, -5, 2, 3};
sort.quickSort(sort.A, 0, sort.A.length-1);
sort.printArr();
Prob3Sum ps = new Prob3Sum();
ps.find3Sum(sort.A);
}
}
#output
Sorted: -5, -1, 0, 2, 3, 5, 9,
Sum: -5 0 5
Sum: -5 2 3