题目描述：
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.
解题分析：
这个和3Sum那道题有些像，也是要先确定两个数，之后两个数的确定可以参考二分查找的实现方法进行优化。
具体代码：
1 public class Solution { 2 public static List<List<Integer>> fourSum(int[] nums, int target) { 3 Arrays.sort(nums); 4 //边界情况的判断 5 List<List<Integer>> results = new ArrayList<List<Integer>>(); 6 if(nums.length<4){ 7 return results; 8 } 9 if(nums.length==4){ 10 if(nums[0]+nums[1]+nums[2]+nums[3]==target){ 11 List<Integer> result = new ArrayList<Integer>(); 12 result.add(nums[0]); 13 result.add(nums[1]); 14 result.add(nums[2]); 15 result.add(nums[3]); 16 results.add(result); 17 18 } 19 return results; 20 } 21 //用遍历方式确定前两个数的位置 22 for(int first=0;first<nums.length-3;first++){ 23 for(int second=first+1;second<nums.length-2;second++){ 24 //第三个数和第四个数用二分查找确定 25 int third=second+1; 26 int fourth=nums.length-1; 27 while(third<fourth){ 28 if(nums[first]+nums[second]+nums[third]+nums[fourth]>target){ 29 fourth--; 30 } 31 else if(nums[first]+nums[second]+nums[third]+nums[fourth]<target){ 32 third++; 33 } 34 else{ 35 List<Integer> result = new ArrayList<Integer>(); 36 result.add(nums[first]); 37 result.add(nums[second]); 38 result.add(nums[third]); 39 result.add(nums[fourth]); 40 results.add(result); 41 //避免元素重复 42 while(third<nums.length-1&&nums[third+1]==nums[third]){ 43 third++; 44 } 45 third++; 46 //避免元素重复 47 while(third<fourth&&nums[fourth-1]==nums[fourth]){ 48 fourth--; 49 } 50 fourth--; 51 52 } 53 } 54 //避免元素重复 55 while(second<nums.length-2&&nums[second+1]==nums[second]){ 56 second++; 57 } 58 } 59 //避免元素重复 60 while(first<nums.length-3&&nums[first+1]==nums[first]){ 61 first++; 62 } 63 } 64 return results; 65 } 66 }