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.

---

Solution 1:递归解法超时，忘记了数组已经排好序，最里层2sum的时候直接用两个指针即可

public class Solution {
    public List<List<Integer>> fourSum(int[] num, int target) {
        Arrays.sort(num);
        List<List<Integer>> res = sub(num, target, 0, 4);
        return res == null ? new ArrayList<List<Integer>>() : res;
    }
 
    private List<List<Integer>> sub(int[] num, int target, int index, int numbers) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (target == 0 && numbers == 0) {
            result.add(new ArrayList<Integer>());
            return result;
        }
        if (numbers < 0 || (index >= num.length || num[index] > target)) {
            return null;
        }
         
        for (int i = index; i < num.length; i++) {
            List<List<Integer>> lists = sub(num, target - num[i], i+1, numbers-1);
            if (lists != null && lists.size() > 0) {
                for (List<Integer> list : lists) {
                    list.add(0, num[i]);
                    result.add(list);
                }
            }
            int tmp = i + 1;
            while (tmp < num.length && num[tmp] == num[i]) {
                tmp++;
            }
            i = tmp - 1;
        }
        return result;
    }
}

Solution 2:
注意最里层对于重复数字的处理，只有当num[start] + num[end] == twoSumTarget满足时，才跳过剩下的重复数字，否则e.g. target＝ 4， 对于［2，2，4］，如果先跳过重复数字的话［2，2］会miss

public class Solution {
    public List<List<Integer>> fourSum(int[] num, int target) {
        Arrays.sort(num);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for (int i = 0; i < num.length; i++) {
            for (int j = i + 1; j < num.length; j++) {
                int twoSumTarget = target - num[i] - num[j];
                int start = j + 1, end = num.length - 1;
                while (start < end) {
                    if (num[start] + num[end] == twoSumTarget) {
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(num[i]);
                        list.add(num[j]);
                        list.add(num[start]);
                        list.add(num[end]);
                        result.add(list);
                        int tmp = start + 1;
                        while (tmp < end && num[tmp] == num[start]) {
                            tmp++;
                        }
                        start = tmp;
                        tmp = end - 1;
                        while (tmp > start && num[tmp] == num[end]) {
                            tmp--;
                        }
                        end = tmp;
                    } else if (num[start] + num[end] < twoSumTarget) {
                        start++;
                    } else {
                        end--;
                    }
                }
                int tmp = j + 1;
                while (tmp < num.length && num[tmp] == num[j]) {
                    tmp++;
                }
                j = tmp - 1;
            }
            int tmp = i + 1;
            while (tmp < num.length && num[tmp] == num[i]) {
                tmp++;
            }
            i = tmp - 1;
        }
        return result;
    }
}

Solution 3:另外一种解法是利用3sum

public class Solution {
    public List<List<Integer>> fourSum(int[] num, int target) {
        Arrays.sort(num);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for (int i = 0 ;i < num.length - 3; i++) {
        	List<List<Integer>> tmp = threeSum(num, i + 1, target - num[i]);
            if (tmp != null && !tmp.isEmpty()) {
                for (List<Integer> list : tmp) {
                    list.add(0, num[i]);
                    result.add(list);
                }
            }
            while (i + 1 < num.length && num[i+1] == num[i]) {
                i++;
            }
        }
        return result;
    }
    private List<List<Integer>> threeSum(int[] num, int index, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for (int i = index; i < num.length - 2; i++) {
            int sum = target - num[i];
            int start = i+1, end = num.length - 1;
            while (start < end) {
                if (num[start] + num[end] == sum) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(num[i]);
                    list.add(num[start]);
                    list.add(num[end]);
                    result.add(list);
                    while (start + 1 < end && num[start+1] == num[start]) {
                        start++;
                    }
                    while (end - 1 > start && num[end-1] == num[end]) {
                        end--;
                    }
                    start++;
                    end--;
                } else if (num[start] + num[end] < sum) {
                    while (start + 1 < end && num[start+1] == num[start]) {
                        start++;
                    }
                    start++;
                } else {
                    while (end - 1 > start && num[end-1] == num[end]) {
                        end--;
                    }
                    end--;
                }
            }
            while (i + 1 < num.length && num[i+1] == num[i]) {
                i++;
            }
        }
        return result;
    }
}