import java.util.Arrays;
/**
* 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).
*
* The solution is to use two nested loops to enumerate the combination of num[i], num[j],
* and then use binary search to locate the numbers which may have the closest distance with the target.
* The complexity of this algorithm is O(n^2*logn).
*/
public class ThreeSumClosest {
public static void main(String[] args) {
int[] a = new int[]{-1, 2, 1, -4};
int target = 1;
int[] result = threeSumClosest(a, target);
System.out.println(Arrays.toString(result));
int[] result1 = threeSumClosest1(a, target);
System.out.println(Arrays.toString(result1));
}
public static int[] threeSumClosest(int[] a, int target) {
int[] result = new int[3];
if (a.length < 3)
return result;
Arrays.sort(a);
int min_distance = Integer.MAX_VALUE;
for (int i = 0; i < a.length - 2; i++) { // extra two element needed, so i