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).
Solution 1: similar as 15, just need to keep updating res if absolute value of res-target is smaller. Remember to sort the array first.
public class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n=nums.length;
int res=0;
int min=Integer.MAX_VALUE;
for (int i=0; i<n-2; i++) {
if (i>0 && nums[i]==nums[i-1]) continue;
int lo=i+1, hi=n-1;
while (lo<hi) {
int sum=nums[i]+nums[lo]+nums[hi];
if (sum==target) return target;
if (Math.abs(sum-target)<min) {
res=sum;
min=Math.abs(sum-target);
}
if (sum>target) hi--;
else lo++;
}
}
return res;
}
}
没有评论:
发表评论