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)

方法

将数组排序，从头開始。先选择一个元素。剩余的元素转换为求解三个数的和。

    public List<List<Integer>> threeSum(int[] num, int start, int target) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        int len = num.length;
        for (int i = start; i < len - 2; i++) {
            if (i == start || num[i] != num[i - 1]) {
                int tempTarget = target - num[i];
                int left = i + 1;
                int right = len - 1;
                while (left < right) {
                    if (left < right) {
                        int temp = num[left] + num[right];
                        if (temp == tempTarget) {
                        	if (left == i + 1 || num[left] != num [left - 1]) {
                                List<Integer> subList = new ArrayList<Integer>();
                                subList.add(num[i]);
                                subList.add(num[left]);
                                subList.add(num[right]);
                                list.add(subList);
                        	}
                            left++;
                            right--;
                        } else if (temp > tempTarget) {
                            right--;
                        } else {
                            left++;
                        }
                    }
    
                }                
            }

        }
        return list;
    }
    
    public List<List<Integer>> fourSum(int[] num, int target) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        Arrays.sort(num);
        int len = num.length;
        for (int i = 0; i < len - 3; i++) {
            if (i == 0 || num[i] != num[i - 1]) {
                int tempTarget = target - num[i];
                List<List<Integer>> tempList = threeSum(num, i + 1, tempTarget);
                for (int j = 0; j < tempList.size(); j++) {
                    List<Integer> subList = tempList.get(j);
                    List<Integer> newList = new ArrayList<Integer>(subList);
                    newList.add(0, num[i]);
                    list.add(newList);
                }
            }
        }
        return list;
    }