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: 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] ]
题目含义：从数组中找4个数字，使得加和等于0，找出所有的组合
1 class Solution { 2 3 4 public List<List<Integer>> threeSum(int[] nums,int target,int firstNumber) { 5 Arrays.sort(nums); 6 List<List<Integer>> res = new LinkedList<>(); 7 for (int i = 0; i < nums.length; i++) { 8 if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) { 9 int low = i + 1, high = nums.length - 1; 10 while (low < high) { 11 if (nums[i] + nums[low] + nums[high] == target) { 12 res.add(Arrays.asList(firstNumber,nums[i], nums[low], nums[high])); 13 while (low < high && nums[low] == nums[low + 1]) low++; 14 while (low < high && nums[high] == nums[high - 1]) high--; 15 low++; 16 high--; 17 } else if (nums[i] + nums[low] + nums[high] > target) high--; 18 else low++; 19 } 20 } 21 } 22 return res; 23 } 24 25 26 public List<List<Integer>> fourSum(int[] nums, int target) { 27 Arrays.sort(nums); 28 List<List<Integer>> res = new LinkedList<>(); 29 if (nums.length==0) return res; 30 int i=0; 31 while (i<nums.length) 32 { 33 if (i<nums.length-1 && nums[i]==nums[i+1]) i++; 34 if (i==nums.length-1) break; 35 int[] rightNums = Arrays.copyOfRange(nums, i, nums.length-1); 36 List<List<Integer>> threeSum = threeSum(rightNums,target-nums[i],nums[i]); 37 res.addAll(threeSum); 38 i++; 39 } 40 return res; 41 } 42 }
原文：http://www.cnblogs.com/wzj4858/p/7732097.html