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 ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function

        ArrayList<ArrayList<Integer>> output = new ArrayList<ArrayList<Integer>>();
        HashSet<ArrayList<Integer>> resultSet = new HashSet<ArrayList<Integer>>();
        if(num.length<4){
            return output;
        }
        Arrays.sort(num);
        for(int i=0;i<num.length-3;i++){
            for(int j=i+1;j<num.length-2;j++){
                int k = j+1;
                int l = num.length-1;
                while(k<l){
                    int sum = num[i]+num[j]+num[k]+num[l];
                    if(sum==target){
                        ArrayList<Integer> result = new ArrayList<Integer>();
                        result.add(num[i]);
                        result.add(num[j]);
                        result.add(num[k]);
                        result.add(num[l]);
                        if(resultSet.add(result)){
                            output.add(result);
                        }
                        k++;
                        l--;
                    }else if(sum<target){
                        k++;
                    }else{
                        l--;
                    }
                }
            }
        }
        return output;

    }

O(N^3) time and O(n^3) space needed. Waiting for more efficient solutions.

Share

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

public int threeSumClosest(int[] num, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int minDiff = Integer.MAX_VALUE;
        int bestSum = -1;
        Arrays.sort(num);
        for(int i=0;i<num.length;i++){
            int twoSum = findClosest(num,i,target);
            int sum = twoSum+num[i];
            if(Math.abs(sum-target)<minDiff){
                minDiff = Math.abs(sum-target);
                bestSum = sum;
            }
        }
        return bestSum;
    }

    public int findClosest(int[] num, int curr, int target){
        int newTarget = target-num[curr];
        int left = 0;
        if(left==curr){
            left++;
        }
        int right = num.length-1;
        if(right==curr){
            right--;
        }
        int minDiff = Integer.MAX_VALUE;
        int bestSum = -1;
        while(left<right){
            int sum = num[left]+num[right];
            if(sum==newTarget){
                return newTarget;
            }
            if(Math.abs(sum-newTarget)<minDiff){
                    minDiff = Math.abs(sum-newTarget);
                    bestSum = sum;
            }
            if(sum<newTarget){
                left++;
                if(left==curr){
                    left++;
                }
            }else{
                right--;
                if(right==curr){
                    right--;
                }
            }
        }
        return bestSum;
    }

The findClosest is a helper function which finds a pair of integers in the given array with the closest sum to the new target num. The new target number is target-num[curr]. Then in the main function, we only need to pick a number as the first integer among the three integers and then use this function to find the closest sum of the rest two integers.

We should first sort the array so that it only takes O(n) for findClosest each time. So the total running time is O(nlgn+n2) = O(n2).

Share