1、前言

2、思路

采用三数之和的思路，原本三数之和可以分解为：数组中的一个数 + 此数右边的数求两数之和，那么四数之和的思路：数组中的一个数 + 此数右边的数求三数之和，有点类似与分治法，分而治之。

3、代码

public class FourSum {

    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            List<List<Integer>> list = threeSumTarget(nums, i + 1, target - nums[i]);
            for (List<Integer> integers : list) {
                integers.add(nums[i]);
                res.add(integers);
            }
            while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++;
        }
        return res;
    }

    private List<List<Integer>> threeSumTarget(int[] nums, int start, int target) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = start; i < nums.length; i++) {
            List<List<Integer>> list = twoSumTarget(nums, i + 1, target - nums[i]);
            for (List<Integer> integers : list) {
                integers.add(nums[i]);
                res.add(integers);
            }
            while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++;
        }

        return res;
    }

    private List<List<Integer>> twoSumTarget(int[] nums, int start, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int left = start, right = nums.length - 1;
        while (left < right){
            int lowNum = nums[left], highNum = nums[right];
            int sum = lowNum + highNum;
            if(sum < target){
                while(left < right && nums[left] == lowNum) left++;
            }else if(sum > target){
                while (left < right && nums[right] == highNum) right--;
            }else if(sum == target){
                List<Integer> list = new ArrayList<>();
                list.add(nums[left]);
                list.add(nums[right]);
                res.add(list);
                while(left < right && nums[left] == lowNum) left++;
                while (left < right && nums[right] == highNum) right--;
            }
        }
        return res;
    }


    public static void main(String[] args) {
        int[] nums = {1,0,-1,0,-2,2};
        int target = 0;
        List<List<Integer>> res = new FourSum().fourSum(nums, target);
        for (List<Integer> re : res) {
            for (Integer integer : re) {
                System.out.print(integer + "    ");
            }
            System.out.println();
        }
    }
}