16. 最接近的三数之和
自己的解法
和三数之和解法类似，先对数组进行排序，然后对计算结果进行比较，结果大于0的话，left++,小于0的话，right--。
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int minDiff = Integer.MAX_VALUE;
int res = 0;
for (int i = 0; i < nums.length; i++) {
int sum = target - nums[i];
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int diff = sum - nums[left] - nums[right];
int diffAbs = Math.abs(diff);
if (diffAbs < minDiff) {
minDiff = diffAbs;
res = nums[i] + nums[left] + nums[right];
}
if (diff > 0) {
left++;
} else if (diff < 0) {
right--;
} else {
return res;
}
}
}
return res;
}
}
进阶解法
思路和自己解法一样，只是在求差值的方式不太一样。
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int ans = nums[0] + nums[1] + nums[2];
for(int i=0;i<nums.length;i++) {
int start = i+1, end = nums.length - 1;
while(start < end) {
int sum = nums[start] + nums[end] + nums[i];
if(Math.abs(target - sum) < Math.abs(target - ans))
ans = sum;
if(sum > target)
end--;
else if(sum < target)
start++;
else
return ans;
}
}
return ans;
}
}
