每天一道leetcode16-最接近的三数之和 分类:数组 中文链接: https://leetcode-cn.com/problems/3sum-closest/description/ 英文链接 https://leetcode.com/problems/3sum-closest/description/
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 例如,给定数组 nums = [-1,2,1,-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
思路
代码
class Solution {
public int threeSumClosest(int[] nums, int target) {
if(nums.length == 3)
return nums[0] + nums[1] + nums[2];
Arrays.sort(nums);
int result = 0;
int cha = Integer.MAX_VALUE;
int tempCha = 0 ;
for(int one=0;one < nums.length-2;one++)
{
int left = one + 1;
int right = nums.length - 1;
while(left < right)
{
int tempSum = nums[one] + nums[left] + nums[right];
tempCha = Math.abs(tempSum - target);
if(tempCha < cha)
{
cha = tempCha;
result = tempSum;
}
if(tempSum == target)
{
return target;
}
if(tempSum < target)
{
left++;
}else{
right--;
}
}
}
return result;
}
}
代码讲解
经验教训
class Solution {
public int threeSumClosest(int[] nums, int target) {
if(nums.length == 3)
return nums[0] + nums[1] + nums[2];
Arrays.sort(nums);
int result = 0;
int one = 0;
int tempSum = nums[one] + nums[1] + nums[nums.length-1];
int cha = Integer.MAX_VALUE;
int left = 1;
int right = nums.length - 1;
int tempCha = 0 ;
for(one=0;one < nums.length-2;one++)
{
left = one + 1;
right = nums.length - 1;
while(left < right)
{
tempSum = nums[one] + nums[left] + nums[right];
tempCha = Math.abs(tempSum - target);
if(tempCha <= cha)
{
cha = tempCha;
result = tempSum;//这里的潜在的最后的正确结果没注意保存
}else{
break;//这里使用了一个break,我以为tempCha大于cha这一层循环就不用了,但是没准往中间逼近的时候和还更小了呢,这里想当然了
}
if(tempSum == target)
{
return target;
}
if(tempSum < target)
{
left++;
}else{
right--;
}
}
}
return result;
}
}