最接近的三数之和
题目描述
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
思路
与#15三数之和一个思路，甚至还简单一点。
直接copy上题代码稍作修改即可
Java实现
class Solution {
public int threeSumClosest(int[] nums, int target) {
int min=Math.abs(nums[0]+nums[1]+nums[2]-target);
int sum=nums[0]+nums[1]+nums[2];
Arrays.sort(nums);
for(int i=0;i<nums.length-2;i++){
if(i>0&&nums[i]==nums[i-1]) continue;
int j=i+1;
int k=nums.length-1;
while(j<k){
int num=Math.abs(nums[i]+nums[j]+nums[k]-target);
if(num<min){
min=num;
sum=nums[i]+nums[j]+nums[k];
}
if(nums[i]+nums[j]+nums[k]<target){
j++;
}
else k--;
}
}
return sum;
}
}
执行用时 : 19 ms, 在3Sum Closest的Java提交中击败了64.32% 的用户。
内存消耗 : 35.8 MB, 在3Sum Closest的Java提交中击败了85.17% 的用户
虽然AC但是结果并不好，要进行优化。
class Solution {
public int threeSumClosest(int[] nums, int target) {
int min=nums[0]+nums[1]+nums[2];
Arrays.sort(nums);
for(int i=0;i<nums.length-2;i++){
if(i>0&&nums[i]==nums[i-1]) continue;
int j=i+1;
int k=nums.length-1;
while(j<k){
int sum=nums[i]+nums[j]+nums[k];
if(sum==target) return sum;
if(Math.abs(sum-target)<Math.abs(min-target)){
min=sum;
}
if(nums[i]+nums[j]+nums[k]<target){
while(j<k&&nums[j]==nums[j+1]) j++;
j++;
}
else{
while(j<k&&nums[k]==nums[k-1]) k--;
k--;
}
}
}
return min;
}
}
执行用时 : 13 ms, 在3Sum Closest的Java提交中击败了87.98% 的用户。
内存消耗 : 35 MB, 在3Sum Closest的Java提交中击败了94.25% 的用户
