leetcode-18-java

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums 
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.

Example:

Given array nums = [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]
]

public static List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    if (null == nums || nums.length < 4) {
        return list;
    }

    Arrays.sort(nums);

    for (int i = 0; i < nums.length - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        int threeTarget = target - nums[i];
        threeSum(nums[i], threeTarget, i+1, nums, list);
    }
    return list;
}

public static void threeSum(int firt, int target, int left, int[] nums, List<List<Integer>> list) {

    for (int i = left; i < nums.length; i++) {
        if (i > left && nums[i - 1] == nums[i]) {
            continue;
        }

        int twoTarget = target -nums[i];
        twoSum(firt, nums[i], twoTarget, i + 1, nums.length - 1, nums, list);
    }
}



private static void twoSum(int first, int second, int target, int left, int right, int[] nums, List<List<Integer>> list) {
    while (left < right) {
        int tmp = nums[left] + nums[right];
        if (tmp == target) {
            list.add(Arrays.asList(first, second, nums[left], nums[right]));
            left ++;
            right --;

            while (left < right && nums[left - 1] == nums[left]) {
                left ++;
            }

            while (left < right && nums[right] == nums[right + 1]) {
                right --;
            }
        } else if (tmp > target) {
            right --;
        } else if (tmp < target) {
            left ++;
        }

    }
}