fourSum:

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.

再多两层循环，此时已经是n立方的时间效率了，尝试了一下，居然也AC了。不知道还有没有更高效的算法。

[java]view plaincopy
				
				import java.util.ArrayList;   
			
				import java.util.Arrays;   
			
				public class FourSum {   
			
				    private ArrayList> list;   
			
				    public ArrayList> fourSum(int[] num, int target) {   
			
				        list = new ArrayList>();   
			
				        Arrays.sort(num);   
			
				        int i = 0;   
			
				        int j = 0;   
			
				        for (i = 0; i <= num.length - 4; i++) {   
			
				            if (i != 0 && num[i] == num[i - 1]) {   
			
				                continue;   
			
				            }   
			
				            for (j = i + 1; j <= num.length - 3; j++) {   
			
				                if (j != i + 1 && num[j] == num[j - 1]) {   
			
				                    continue;   
			
				                }   
			
				                judgeAndPut(num, i, j, j + 1, num.length - 1, target);   
			
				            }   
			
				        }   
			
				        return list;               
			
				    }   
			
				    private void judgeAndPut(int[] num, int i, int j, int p, int q, int target) {   
			
				        while (p < q) {   
			
				            int sum = num[i] + num[j] + num[p] + num[q];   
			
				            if (sum < target) {   
			
				                p++;   
			
				            } else if (sum > target){   
			
				                q--;   
			
				            } else if (sum == target) {   
			
				                ArrayList tmpList = new ArrayList();   
			
				                tmpList.add(num[i]);   
			
				                tmpList.add(num[j]);   
			
				                tmpList.add(num[p]);   
			
				                tmpList.add(num[q]);   
			
				                list.add(tmpList);   
			
				                p++;   
			
				                q--;   
			
				                while (p < q && num[p] == num[p - 1]) {   
			
				                    p++;   
			
				                }   
			
				                while (p < q && num[q] == num[q + 1]) {   
			
				                    q--;   
			
				                }   
			
				            }   
			
				        }   
			
				    }   
			
				    public static void main(String[] args) {   
			
				        int num[] = {-1,0,1,0,-2,2};   
			
				        System.out.println(new FourSum().fourSum(num, 0));   
			
				    }   
			
				}

ITPub博客

算法4Sum

最新文章