4Sum

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:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
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个数，在数组中找出所有和等于这个目标值的4个数，不允许重复，以非递减顺序排列这四个数

题目难度：Medium

import java.util.*;

/**
 * Created by gzdaijie on 16/5/18
 * 类似于15题——3sum, 多加一层循环
 * 先以O(N*N)的复杂度枚举可能出现的2个数的组合, 再按照3sum的解法寻找和为target的另外2个数
 * 总的时间复杂度O(N*N*N)
 */
public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int len = nums.length;
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (len < 4) return result;

        Arrays.sort(nums);
        for (int i = 0; i < len - 3; i++) {
            if (i != 0) {
                while (i < len - 3 && nums[i] == nums[i - 1]) i++;
            }

            for (int j = i + 1; j < len - 2; j++) {
                if (j != i + 1) {
                    while (j < len - 2 && nums[j] == nums[j - 1]) j++;
                }

                int left = j + 1;
                int right = nums.length - 1;
                int sum = nums[i] + nums[j];
                while (left < right) {
                    int total = sum + nums[left] + nums[right];
                    if (total == target) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        ++left;
                        while (left < right && nums[left] == nums[left - 1]) ++left;
                    } else if (total < target) {
                        ++left;
                    } else {
                        --right;
                    }

                }
            }
        }
        return result;
    }
}

参考：15.3Sum