Leetcode 16: 3Sum Closest

Problem: 

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:

This problem is similar to 3Sum, instead we have to track the minimum gap during the process. The process of doing 3sum is the same:

Step 1: Sort the given array from low to high. 

Step 2: Get the sum of three different elements each time by using three pointers

           P1: traverse the array from the first element to the end-2. For each P1, another pointer P2                     points to the next element of P1 while the third pointer P3  points to the last element. 

Step 3: For each summation, keep tracking the minimum gap between the summation and the target,             and update the 

You may wonder why the three pointer algorithm achieves the minimum running time. The reason is that the first step make sure the each time, P1 points to a different value so that the combination of P1, P2 and P3 (P1<P2<P3) will never be traversed twice. Also,  you can consider this problem as a problem selecting three different elements from an array and then return the combinations.

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        if(num==null || num.length<3){
            return -1;
        }
        int gap=Integer.MAX_VALUE;
        int temp=-1;
        Arrays.sort(num);
        for(int i=0;i<num.length;i++){
            int j=i+1;
            int k=num.length-1;
            while(j<k){
                int sum=num[i]+num[j]+num[k];
                if(Math.abs(target-sum)<gap){
                    gap=Math.abs(target-sum);
                    temp=sum;
                }
                if(sum<target){
                    j++;
                }else{
                    k--;
                }
            }
        }
        return temp;
    }
}