3Sum Closest (Java)

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.

	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).
	// 2/18/2014 code rewrite
	public class Solution {
	public int threeSumClosest(int[] num, int target) {
	if (num==null||num.length==0){
	return -1;
	}
	int result=0;
	int minDif=Integer.MAX_VALUE;
	Arrays.sort(num);
	for (int i=0; i<num.length-2; i++ ){
	int first=num[i];
	int left=i+1;
	int right=num.length-1;
	while (left<right){
	int value=first+num[left]+num[right];
	if (value==target){
	return value;
	}
	int diff=Math.abs(value-target);
	if (diff<minDif){
	result=value;
	minDif=diff;
	}
	if (value>target){
	do {right--;} while(left<right && num[right]==num[right+1]);
	}
	else if (value<target){
	do {left++;} while (left<right && num[left]==num[left-1]);
	}
	}
	}
	return result;
	}
	}
	public class Solution {
	public int threeSumClosest(int[] num, int target) {
	// Start typing your Java solution below
	// DO NOT write main() function
	Arrays.sort(num);
	int min=Integer.MAX_VALUE;
	int result=0;
	for (int i=0; i<num.length; i++){
	if (i>0&&num[i]==num[i-1]) continue;
	int start=i+1;
	int end=num.length-1;
	while(start<end){
	int sum=num[i]+num[start]+num[end];
	if (sum>target){
	int diff=sum-target;
	if (diff<min){
	min=diff;
	result=sum;
	}
	do {end--;} while(start<end && num[end]==num[end+1]);
	}
	else if (sum<target){
	int diff=target-sum;
	if (diff<min){
	min=diff;
	result=sum;
	}
	do {start++;} while(start<end&& num[start]==num[start-1]);
	}
	else{
	min=0;
	result=sum;
	break;
	}
	}
	}
	return result;
	}
	}

view raw 3 Sum Closest .java hosted with ❤ by GitHub