用 PHP 来刷leetCode 之 最接近的三数之和

本文主要是介绍用 PHP 来刷leetCode 之 最接近的三数之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2)

 

先排序, 然后遍历, 然后内部使用双指针, 时间复杂度应该是O(n²), 代码如下:

 

/*** @param $nums* @param $target* @return int*/
function threeSumClosest($nums, $target) {$count = count($nums);if($count < 3){return 0;}if($count == 3){return array_sum($nums);}sort($nums);$res = $nums[0]+$nums[1]+$nums[$count-1];for ($i = 0;$i <= $count-3;$i++){$j = $i+1;$k = $count-1;while ($k > $j){$tmpSum = $nums[$j]+$nums[$k]+$nums[$i];//如果相等 就直接返回target 跳出循环if($tmpSum === $target){return $target;}if(abs($target-$nums[$i]-$nums[$j]-$nums[$k])<abs($target-$res)){$res = $nums[$i]+$nums[$j]+$nums[$k];}if($tmpSum < $target){$j++;}else{$k--;}}}return $res;
}echo threeSumClosest([0,1,1,1],-100);

 

这篇关于用 PHP 来刷leetCode 之 最接近的三数之和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---