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.
