[leet code] 3Sum Closest

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).      

==========

Analysis:

The most basic approach, try all the possible combinations to find out the most closest one. O(n^3)

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        if(num.length == 0) return 0;
        if(num.length == 1) return num[0];
        if(num.length == 2) return num[0] + num[1];

        int minSum=0;
        for(int i=0; i<num.length-2; i++){
            for(int j=i+1; j<num.length-1; j++){
                for(int k=j+1; k<num.length; k++){
                    int sumTemp = num[i]+num[j]+num[k];
                    minSum=Math.min(Math.abs(sumTemp-target), minSum);
                }
            }
        }
        return minSum;
    }
}
           

A better solution can be started from 2Sum problem.  In which we can first of all, sort the array.  Then setup 2 pointers, one point to the beginning of the array (smallest value), another point to the end of the array (biggest value). Then in each iteration, we compute the sum of these two value and compare with the target number.  If equal, return.  Else if less then target number, move left pointer to the right next element.  Else (sum value larger than the target value) move the right pointer to the left next element.  

When we have the solution for 2Sum problem, we can decrease the 3Sum problem to 2Sum problem by choosing a 3rd int then solve the 2Sum problem.  After we went through all the the elements in the array as 3rd int.  We can return the sum that closest to the target number.

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        if(num.length == 0) return 0;
        if(num.length == 1) return num[0];
        if(num.length == 2) return num[0] + num[1];
        
        // sort original array
		Arrays.sort(num);
        
        int minDef = Integer.MAX_VALUE;
        int treeSum = 0;
        for (int i=0; i<num.length; i++){
            if(Math.abs(num[i]+twoSumClosest(num, target-num[i], i)-target)<minDef){
                minDef = Math.abs(num[i]+twoSumClosest(num, target-num[i], i)-target);
                treeSum = num[i]+twoSumClosest(num, target-num[i], i);
            }
        }
        return treeSum;
    }
    
    // 2Sum closest solution
    public int twoSumClosest(int[] num, int target, int thirdInt){
        int leftPointer=0;
        if(leftPointer == thirdInt) leftPointer++;  // 3rd int located at the beginning of array
        
        int rightPointer=num.length-1;
        if(rightPointer == thirdInt) rightPointer--; // 3rd int located at the end of array
        
        int minTwoDef = Integer.MAX_VALUE;
        int twoSum = 0;
        
        while(leftPointer<rightPointer){
            int sumTemp = num[leftPointer] + num[rightPointer];
            
            if(sumTemp == target) return sumTemp;
            else if(sumTemp>target){
                rightPointer--;
                if(rightPointer == thirdInt) rightPointer--;
            }
            else{
                leftPointer++;
                if(leftPointer == thirdInt) leftPointer++;
            }
            
            if(Math.abs(sumTemp-target)<minTwoDef){
                minTwoDef = Math.abs(sumTemp-target);
                twoSum = sumTemp;
            }
        }
        return twoSum;
    }
}
           

An optimized solution is that, 2Sum solution does not need to perform on all the element in the array.  After choosing the 3rd int, we need only perform the 2Sum solution on the ints after the chosen 3rd int.  For example, in array [1,2,3,4,5,6,7], if we chose 3 as the 3rd int, we need only perform 2Sum among [4,5,6,7].  This is because case of [1,2,3] has been tried when we chose 1 as the 3rd int.

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        if(num.length == 0) return 0;
        if(num.length == 1) return num[0];
        if(num.length == 2) return num[0] + num[1];
        
        // sort original array
        Arrays.sort(num);
        
        int minDef = Integer.MAX_VALUE;
        int treeSum = 0;
        for (int i=0; i<num.length-2; i++){
            if(Math.abs(num[i]+twoSumClosest(num, target-num[i], i)-target)<minDef){
                minDef = Math.abs(num[i]+twoSumClosest(num, target-num[i], i)-target);
                treeSum = num[i]+twoSumClosest(num, target-num[i], i);
            }
        }
        return treeSum;
    }
    
    // 2Sum closest solution
    public int twoSumClosest(int[] num, int target, int thirdInt){
        int leftPointer=thirdInt+1;
        int rightPointer=num.length-1;

        int minTwoDef = Integer.MAX_VALUE;
        int twoSum = 0;
        
        while(leftPointer<rightPointer){
            int sumTemp = num[leftPointer] + num[rightPointer];
            
            if(sumTemp == target) return sumTemp;
            else if(sumTemp>target) rightPointer--;
            else leftPointer++;
            
            if(Math.abs(sumTemp-target)<minTwoDef){
                minTwoDef = Math.abs(sumTemp-target);
                twoSum = sumTemp;
            }
        }
        return twoSum;
    }
}
           

Reference: 求和問題總結(leetcode 2Sum, 3Sum, 4Sum, K Sum)