Find all b[k]=a[i]+a[j] for the given array a. Iterate over all elements of this array b. Let the sum be (a+b). Now binary search (target - (a+b) ) in the array b.
Complexity : O( (N^2)( log (N^2) ) ) Correct me if i am wrong. On Fri, Jun 15, 2012 at 8:41 PM, Amol Sharma <amolsharm...@gmail.com> wrote: > O(n^3) is straight forward: > > find all triplets and store them in an array say sum. > and then for each triplet do binary search for (target-sum[i]) in the > given array. > > > is solution better than O(n^3) possible ? > -- > > > Amol Sharma > Final Year Student > Computer Science and Engineering > MNNIT Allahabad > > <http://gplus.to/amolsharma99> > <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/><http://facebook.com/amolsharma99> > > > > > > > On Fri, Jun 15, 2012 at 6:53 PM, Karthikeyan V.B <kartmu...@gmail.com>wrote: > >> Complexity : O(n^3) >> >> >> import java.util.*; >> >> public class Solution { >> >> public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) { >> >> // Start typing your Java solution below >> >> // DO NOT write main() function >> >> ArrayList<ArrayList<Integer>> arr=new ArrayList<ArrayList<Integer>>(); >> >> Arrays.sort(num); >> >> int n=num.length; >> >> int sum=0; >> >> for(int i=0;i<n-3;i++) >> >> { >> >> int a=num[i]; >> >> for(int j=i+1;j<n-2;j++) >> >> { >> >> int b=num[j]; >> >> int k=j+1; >> >> int l=n-1; >> >> while(k<l) >> >> { >> >> int c=num[k]; >> >> int d=num[l]; >> >> if(a+b+c+d < target) >> >> k++; >> >> else if(a+b+c+d > target) >> >> l--; >> >> else >> >> { >> >> ArrayList<Integer> al=new ArrayList<Integer>(); >> >> al.add(a); >> >> al.add(b); >> >> al.add(c); >> >> al.add(d); >> >> if(!arr.contains(al)) >> >> arr.add(al); >> >> k++; >> >> } >> >> } >> >> } >> >> } >> >> return arr; >> >> } >> >> } >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Hemesh singh -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
