The idea is same as 3Sum, but add a distance check and update the result each time/approach. Watch how the loop work. This one doesn't case duplicates anyway better to have.
public class Solution {
public int threeSumClosest(int[] num, int target) {
if(num == null || num.length < 3){
return Integer.MIN_VALUE;
}
Arrays.sort(num);
int i = 0;
int result = num[0] + num[1] + num[2];
int distance = Integer.MAX_VALUE;
while(i < num.length - 2){
int curTarget = target - num[i];
int start = i + 1;
int end = num.length - 1;
while(start < end){
if(Math.abs(num[start] + num[end] - curTarget) < distance){
distance = Math.abs(num[start] + num[end] - curTarget);
result = num[start] + num[end] + num[i];
}
if(num[start] + num[end] < curTarget){
start++;
}else if(num[start] + num[end] > curTarget){
end--;
} else{
return target;
}
}
i++;
}
return result;
}
}
没有评论:
发表评论