Question:Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
- Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
- The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)
给定一个n个数的数组S,判断存在不存在这样的a,b,c,d使a+b+c+d=target,找出所有的符合条件的值,注意,必须满足a<=b<=c<=d,举个例子说,比如数组S={1,0,-1,0,-2,2}target=0,
那么答案是(-1, 0, 0, 1)(-2, -1, 1, 2) (-2, 0, 0, 2)。
算法思路:① 这个题和上两篇文章三个数的和类似http://www.cnblogs.com/zhaolizhen/p/3Sum.html,上两篇用的是穷举算法,这次总不能再用穷举吧,下面是比较好理解时间复杂度又
比较小的一种算法。
② 首先对数组进行排序,设置两个for循环,作为四个数中的前两个数,有可能有两个相同的数,遇到相同的数跳过,这样做是为了避免重复。
③ 四个数中的后两个数怎么办,通过设置两个指针m和n,m从数组前往后进行遍历,n用来从数组后往前进行遍历。m>=n是结束循环的条件。
④ 遇到target==a+b+c+d的数就加到Arraylist中.
代码设计():
1 class Solution{ 2 public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) { 3 // 4个数的和再使用穷举算法时间复杂度就太高了 4 ArrayList <ArrayList<Integer>> arrayList=new ArrayList<ArrayList<Integer>>();//最终返回的容器类型 5 Arrays.sort(num); 6 for(int i=0;i<num.length;i++){//三重循环时间复杂度太高, 可是也没想起其他好办法 7 if(i!=0&&num[i]==num[i-1]) 8 continue;//如果两个数连着相等,直接越过这个数就可以 9 for(int j=i+1;j<num.length;j++){ 10 if(j!=i+1&&num[j]==num[j-1]) 11 continue; 12 //到现在为止已经加了两个数 13 int m=j+1;//m从左边扫描 14 int n=num.length-1;//n从右边扫描 15 int sum; 16 while(m<n){//m n扫描数组 17 sum=num[i]+num[j]+num[m]+num[n]; 18 if(m!=j+1&&num[m]==num[m-1]) 19 m++; 20 else if(n!=num.length-1&&num[n]==num[n+1]) 21 n--; 22 else if(target<sum) 23 n--; 24 else if(target>sum) 25 m++; 26 else if(target==sum){//符合条件加到arraylist 27 ArrayList<Integer> list=new ArrayList <Integer>(); 28 list.add(num[i]); 29 list.add(num[j]); 30 list.add(num[m]); 31 list.add(num[n]); 32 Collections.sort(list); 33 arrayList.add(list); 34 m++; 35 n--; 36 } 37 38 } 39 } 40 } 41 return arrayList; 42 } 43 }
此算法参考了http://www.cnblogs.com/remlostime/archive/2012/10/27/2742676.html,不过他是用C++实现,其思想是一样的。2013-10-20