您的位置:首页 > 房产 > 家装 > app 软件开发公司_沧州网站建设公司翼马_百度如何免费打广告_海南网站建设

app 软件开发公司_沧州网站建设公司翼马_百度如何免费打广告_海南网站建设

2024/12/23 3:00:03 来源:https://blog.csdn.net/u014165391/article/details/144199346  浏览:    关键词:app 软件开发公司_沧州网站建设公司翼马_百度如何免费打广告_海南网站建设
app 软件开发公司_沧州网站建设公司翼马_百度如何免费打广告_海南网站建设

题目描述:

给你一个长度为 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
解释:与 target 最接近的和是 0(0 + 0 + 0 = 0)。

解题思路:

本题目因为要计算三个数,如果靠暴力枚举的话需要3层遍历,时间复杂度会到 O(n3),这是不推荐的,直接说结果吧,需要采用双指针算法,描述如下:

双指针算法
  • 先让数组有序,也就是需要先对数组进行排序
  • 然后每次固定一个元素,再去寻找另外两个元素,也就是双指针

双指针法的代码实现:

1.使用sort方法对数组进行排序

2.假设结果值result是一个无穷大Infinity;
3.每次遍历的过程中设置两个指针,分别是 left = i + 1、right = nums.length - 1。
4.检查 sum = nums[i] + nums[left] + nums[right]与 target 的距离,如果该距离比之前保存的 result 与 target 的距离更小,就更新 result。
5.然后就是移动双指针。
6.如果 sum 的值比 target 大,那么我们让 right--,因为数组是有序的,right --会使得下一次的 sum 更小,也就更接近 target 的值
7.同理,如果 sum 的值 target 小,那么我们让 left++。·
8.left++ 和 right-- 的界限是 left < right,一是保证:left和right索引对应的不能是同一个值(题目要求left, right是2个值) 二是如果 left > right, left的索引会越界(导致while循环赋值比较逻辑出错)
9.如果sum != target,则会返回result (每次遍历:会根据Math.abs绝对值比较选择最小)

 function threeSumClosest(nums, target) {nums.sort((a, b) => a - b) // 1.先对nums递增排序let result = Infinity; // 2.假设结果值是一个无穷大(假想值)for (let i = 0; i < nums.length; i++) { // 3.遍历numslet left = i + 1; // 第二个值设置为下一个索引(左指针:代表较小值)let right = nums.length - 1; // 第三个值设置为最后一个索引(右指针:代表较大值)while (left < right) { // 4. 此处保证:1)left和right索引对应的不能是同一个值(题目要求left, right是2个值) 2) right索引对应值必须比left索引对应值大let sum = nums[i] + nums[left] + nums[right] // 5.三个值求和if (Math.abs(sum - target) < Math.abs(result - target)) { // 6.sum-target可能是一个负值(负值数字越小反而值越大),所以取绝对值比较result = sum // 7.如果Math.abs(sum - target) < Math.abs(result - target),则说明sum离目标值target距离越小,也就是更接近目标值,所以此时将最接近sum值更新给result}if (sum < target) { // 如果当前求和的sum值 < 目标值target, 说明离目标值距离还不够接近,让左指针index++,往中间靠拢,值会变大left++;} else if (sum > target) { // 如果当前求和的sum值 > 目标值target, 说明离目标值距离超过了,让右指针index--,往中间靠拢,值会变小right--;} else {return sum; // 如果当前求和的sum值 === 目标值target,则达成要求,直接返回sum}}}return result; // 如果求和sum值没有等于目标值target,则返回最接近的值};const nums = [-1, 2, 1, -4];const target = 1;const closestNum = threeSumClosest(nums, target);console.log(closestNum); // 输出结果为 2

图解实现:

1.排序

2. for循环遍历判断

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com