不解释了，直接上代码，代码详细注释。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
//使用双指针法，首先排序
Arrays.sort(nums);
List<List<Integer>> res = new LinkedList<>();
for(int i = 0; i < nums.length; ++i){
List<List<Integer>> tmp = threeSum(nums, i + 1, target - nums[i]);
for(List<Integer> tuple : tmp){
tuple.add(nums[i]);
res.add(tuple);
}
//下面这个while为什么不能放到前面呢？
//因为先找第一个数是target的三元组，如果先把指针移动到最后一个相同元素去寻找，
//那么结果中将缺少，含有相同元素，但是正确答案的三元组。
while(i < nums.length - 1 && nums[i] == nums[i + 1]) i++;
}
return res;
}
//3sum问题
public List<List<Integer>> threeSum(int[] nums, int start, int target) {
List<List<Integer>> res = new LinkedList<>();
for(int i = start; i < nums.length; ++i){
List<List<Integer>> tmp = twoSum(nums, i + 1, target - nums[i]);
for(List<Integer> tuple : tmp){
tuple.add(nums[i]);
res.add(tuple);
}
//下面这个while为什么不能放到前面呢？
//因为先找第一个数是target的三元组，如果先把指针移动到最后一个相同元素去寻找，
//那么结果中将缺少，含有相同元素，但是正确答案的三元组。
while(i < nums.length - 1 && nums[i] == nums[i + 1]) i++;
}
return res;
}
//twoSum问题
public List<List<Integer>> twoSum(int[] nums, int start,int target){
int lo = start;
int rh = nums.length - 1;
List<List<Integer>> res = new LinkedList<>();
while(lo < rh){
int left = nums[lo];
int right = nums[rh];
int sum = nums[lo] + nums[rh];
if(sum < target){
//这里所有的while都是为了去重。
//例如：1， 2， 2，3 使用了2后，要移动到3.
while(lo < rh && nums[lo] == left) lo ++;
}else if(sum > target){
while(lo < rh && nums[rh] == right) rh --;
}else{
List<Integer> tmp = new LinkedList<>();
tmp.add(left);
tmp.add(right);
res.add(tmp);
while(lo < rh && nums[lo] == left) lo ++;
while(lo < rh && nums[rh] == right) rh --;
}
}
return res;
}
}
