16. 最接近的三数之和
题目描述
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
方法：排序+双指针
本题与三数之和类似，都可以使用排序+双指针的方式来实现。
- 其实最简单可以使用三层循环暴力求解，但是这样时间复杂度比较高。
- 排序+双指针
- 将数组排序，然后每次考虑第一个元素
a以后，对于剩下的元素b和c，我们希望它们的值接近于target-a。 - 我们可以将
b从a所在元素的下一个开始，c从最后一个元素开始，同时遍历。- 若
a+b+c=target，则直接返回。 - 若
a+b+c!=target，则判断与target之间插值绝对值的大小。同时判断与target的大小关系：- 若
a+b+c<target，则c所在的指针向前移动。 - 若
a+b+c>target，则b所在的指针向后移动。
- 若
- 若
- 将数组排序，然后每次考虑第一个元素
class Solution {
public int threeSumClosest(int[] nums, int target) {
int best = 10000000;
Arrays.sort(nums);
int length = nums.length;
for (int first=0;first<length;++first){
if (first>0 && nums[first]==nums[first-1]){
continue;
}
int second = first + 1, third = length - 1;
while (second < third){
int curr = nums[first] + nums[second] + nums[third];
if (curr == target){
return curr;
}
if (Math.abs(curr-target) < Math.abs(best-target)){
best = curr;
}
if (curr < target){
int j = second + 1;
while (j<third && nums[j]==nums[second]){
++j;
}
second = j;
} else {
int k = third - 1;
while (k>second && nums[k]==nums[third]){
--k;
}
third = k;
}
}
}
return best;
}
}
若定义
int best = Integer.MAX_VALUE则无法通过，有一个用例一直会报错。数组是-3,-2,-5,3,-4, target 为-1。是因为 best减去复数超出了 Integer 的范围了吗？