题目描述:给你一个长度为 n 的整数数组 nums 和 一个目标值 target 。请你从 nums 中选出三个整数，使它们的和与 target 最接近。 返回这三个数的和。 假定每组输入只存在恰好一个解。 示例 1:输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2:输入：nums = [0,0,0], target = 1
输出：0
提示:题目分析:这道题基本和 LeetCode 15.三数之和(中等) 一样，只不过需要多加个差值计算，判断当前和是否接近目标值。具体的思路还是使用双指针，先定义一个变量存放结果值，对数组进行排序，定义左右两个指针，循环数组。先固定一个数，微调左右指针指向的元素，计算三个索引上的数之和，这里要加个比较，判断当前和与目标值之间的差值是否比旧的结果值与目标值之间的差值更小，如果更小说明该和更接近目标值，要对结果进行更新。 题解:执行用时: 5 ms 内存消耗: 38 MB class Solution {
public int threeSumClosest(int[] nums, int target) {
// 获取数组长度
int length = nums.length;
// 因题目条件已经给了数组必定大于等于 3 所以小于 3 的情况不用考虑
// 当数组长度刚好等于 3
if (length == 3) {
// 直接返回这三个元素的和
return nums[0] + nums[1] + nums[2];
}
// 数组长度大于 3 首先对数组进行排序
Arrays.sort(nums);
// 定义一个结果值
int res = 10000;
// 循环遍历数组
for (int i = 0; i < length; ++i) {
// 如果当前固定数和前一个相同
if (i > 0 && nums[i] == nums[i - 1]) {
// 直接跳过该数 目的是为了去重
continue;
}
// 定义左索引
int left = i + 1;
// 定义右索引
int right = length - 1;
// 当左索引小于右索引值时遍历右区间
while (left < right) {
// 计算固定索引上的值与左右索引上的值之和
int sum = nums[i] + nums[left] + nums[right];
// 如果和刚好等于目标值 直接返回即可
if (sum == target) {
return target;
}
// 计算当前和与目标值 结果值与目标值的绝对值
// 如果当前和与目标值的差值还比旧的结果值与目标值的差还小
// 说明当前和更接近目标值
if (Math.abs(sum - target) < Math.abs(res - target)) {
// 更新结果值
res = sum;
}
// 如果当前和大于目标值
if (sum > target) {
// 要使当前和更接近目标值
// 就得使和更小 所以右索引要左移
// 获取右索引左移一位的索引值
int j = right - 1;
// 当新的右索引值大于左索引值 并且 新的右索引上的值与旧的右索引上的值相同
while (left < j && nums[j] == nums[right]) {
// 跳过该值 目的同样是为了去重
--j;
}
// 更新右索引值
right = j;
} else {
// 否则当前和小于等于目标值
// 要使当前和更接近目标值
// 就得使和更大 所以左索引要右移
// 获取左索引右移一位的索引值
int j = left + 1;
// 当新的左索引值小于右索引值 并且 新的左索引上的值与旧的左索引上的值相同
while (j < right && nums[j] == nums[left]) {
// 跳过该值 目的同样是为了去重
++j;
}
// 更新左索引值
left = j;
}
}
}
// 返回结果
return res;
}
}
|
