18.4Sum
题目大意：与3sum类似，只是这里是四个数之和等于target，找出所有满足条件的组合。
法一：三层循环，使用3sum的方法，只是外面再嵌套一层循环即可。注意去重。代码如下（耗时43ms）：
1 public List<List<Integer>> fourSum(int[] nums, int target) { 2 Arrays.sort(nums); 3 List<List<Integer>> res = new ArrayList<List<Integer>>(); 4 for(int i = 0; i < nums.length - 3; i++) { 5 //去除重复值 6 if(i != 0 && nums[i] == nums[i - 1]) { 7 continue; 8 } 9 for(int j = i + 1; j < nums.length - 2; j++) { 10 int left = j + 1, right = nums.length - 1; 11 while(left < right) { 12 int sum = nums[i] + nums[j] + nums[left] + nums[right]; 13 if(sum < target) { 14 left++; 15 } 16 else if(sum > target) { 17 right--; 18 } 19 else { 20 List<Integer> listIn = new ArrayList<Integer>(); 21 listIn.add(nums[i]); 22 listIn.add(nums[j]); 23 listIn.add(nums[left]); 24 listIn.add(nums[right]); 25 res.add(listIn); 26 //去除重复值 27 while(left < right && nums[left] == nums[left + 1]) { 28 left++; 29 } 30 while(left < right && nums[right] == nums[right - 1]) { 31 right--; 32 } 33 left++; 34 right--; 35 } 36 } 37 //去除重复值 38 while(j + 1 < nums.length - 2 && nums[j] == nums[j + 1]) { 39 j++; 40 } 41 } 42 } 43 return res; 44 }