描述：给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
最接近目标值的三数之和，若是用穷举法，需要三重遍历会过于低效，而为了减少遍历层数，同时让可以遍历所有元素,可以尝试用三指针法，获取三个数之和，保留最小的那个，这样只需要遍历最小的那个数的索引值，之后通过while实现左、右指针的循环移动即可实现遍历数组的三数之和。
var threeSumClosest = function (nums, target) {
if (nums.length< 3) {
return null;
}
nums = nums.sort( (a,b)=> a-b );
for(var i=0;i<nums.length-2;i++){
var min = nums[0]+nums[1]+nums[2] - target;
var l=i+1,r=nums.length-1;
while(l<r){
var sum = nums[i]+nums[l]+nums[r];
if(sum == target){
return sum;
}else if(sum>target){
--r;
}else{
++l;
}
if(Math.abs(min)>Math.abs(sums-target)){
min = sums-target;
}
} //while循环结束
}
return min+target;
}
这种方法我觉得仍然有改进的余地，比如当min开始变大的时候完全可以跳出本次循环，小伙伴们觉得这种优化能实现吗？当然不能，因为数与数之间的间隔是变量，无法掌控，很有可能在接近目标值的时候，总数不够，l下标的元素右移，导致min变大，此时已经跳出了循环，然而，当r的下标左移时，min取得最小值。
那么优化1：把重复的元素不计入其中。
在for循环里面加入if(nums[i]==nums[i-1]) continue
优化2：在left指针位置确定后，若当前最小值大于target，则只需考虑最小值为总数时，算出差值min，当right指针位置确定后，若当前最大值小于target，则只需考虑最小值为总数的情况，并算出差值min。
var threeSumClosest = function (nums, target) {
if (nums.length< 3) {
return null;
}
nums = nums.sort( (a,b)=> a-b );
var diff = Math.abs( nums[0]+nums[1]+nums[2]- target);
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = nums.length - 1;
int rangeMin = nums[i] + nums[left] + nums[left + 1];
int rangeMax = nums[i] + nums[right] + nums[right - 1];
if (rangeMin > target) {
if (Math.abs(rangeMin - target) < diff) {
diff = Math.abs(rangeMin - target);
result = rangeMin;
}
continue;
} else if (rangeMax < target) {
if (Math.abs(rangeMax - target) < diff) {
diff = Math.abs(rangeMax - target);
result = rangeMax;
}
continue;
}
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
result = target;
return result;
}
if (Math.abs(sum - target) < diff) {
diff = Math.abs(sum - target);
result = sum;
}
}
}
return result;
}
网友评论