题目:最接近的三数之和
要求:给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如 :
输入:nums = [-1,2,1,-4], 1
输出:2 (-1 + 2 + 1 = 2)
解题思路:
- 对给定的数组排序,再使用双指针找出与target和最接近的三数之和
- 注意:与target最接近之数与target之间的差可能为正数也可能为负数
题解代码如下:
class Solution {
private static int threeSumClosets(int[] nums, int target) {
if (null == nums || nums.length < 3) {
throw new UnsupportedOperationException("nums length is not enough");
}
Arrays.sort(nums);
int length = nums.length;
int ans = nums[0] + nums[1] + nums[2];
for (int i = 0; i < length; i++) {
int left = i + 1;
int right = length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (Math.abs(target - sum) < Math.abs(target - ans)) {
ans = sum;
} else if (sum < target) {
left ++;
} else if (sum > target) {
right--;
} else {
return ans;
}
}
}
return ans;
}
}