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:
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)
解题思路：
4个指针， 前两个指针双循环遍历数组，第三个指针放在第二个指针之后，第四个指针放在末尾，求和和target比较，如果 sum > target 最后一个指针--， 如果sum < target 第三个指针++; 相等先判断是否是重复的（hashset）,如果不是添加到result中去；
1 public class Solution { 2 public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) { 3 Arrays.sort(num); 4 ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); 5 HashSet<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>(); 6 int len = num.length; 7 for(int i = 0; i< len; i++){ 8 for(int j = i+1; j < len; j++){ 9 int k = j+1; 10 int l = len-1; 11 12 while(k < l){ 13 int sum = num[i]+num[j]+num[k]+num[l]; 14 15 if(sum < target){ 16 k++; 17 }else if(sum > target){ 18 l--; 19 }else { 20 ArrayList<Integer> output = new ArrayList<Integer>(); 21 output.add(num[i]); 22 output.add(num[j]); 23 output.add(num[k]); 24 output.add(num[l]); 25 if(! set.contains(output)){ 26 set.add(output); 27 result.add(output); 28 } 29 k++; 30 l--; 31 } 32 } 33 } 34 } 35 36 return result; 37 38 } 39 }
原文：http://www.cnblogs.com/RazerLu/p/3547917.html
