
16 最接近的三数之和(排序、双指针)
排序数组:首先对数组进行排序,这有助于使用双指针技巧高效地找到最接近的和。 检查边界情况:如果目标值小于或等于前三个元素的和,或者大于或等于后三个元素的和,可以直接返回对应的和,因为这两个和是可能的最接近值。 初始化变量:设置一个变量来记录当前找到的最接近和,初始值为最大整数。 使用双指针技巧:从数组的第四个元素开始,设左指针在该位置,右指针在数组末尾。根据当前和与目标值的比较,移动指针以缩小差距。 更新最接近值:每次计算当前和时,检查其与目标值的差距,如果比已记录的最接近值更小,则更新最接近值。 返回结果:在遍历结束后,返回最接近值。
发布日期:2021-05-07 21:50:44
浏览次数:8
分类:精选文章
本文共 1947 字,大约阅读时间需要 6 分钟。
为了找到数组中三个整数,使其和与目标值最接近,我们可以采用以下步骤:
以下是具体的实现代码:
import java.util.Arrays;class Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int len = nums.length; int closest = Integer.MAX_VALUE; // 检查前三个和后三个的和 int firstSum = nums[0] + nums[1] + nums[2]; if (target <= firstSum) { return firstSum; } int lastSum = nums[len - 3] + nums[len - 2] + nums[len - 1]; if (target >= lastSum) { return lastSum; } // 遍历数组,使用双指针技巧 for (int a = 0; a <= len - 3; a++) { // 跳过重复的元素 if (a > 0 && nums[a] == nums[a - 1]) { continue; } int b = a + 1; int c = len - 1; while (b < c) { int currentSum = nums[a] + nums[b] + nums[c]; if (currentSum == target) { return target; } int diffCurrent = Math.abs(target - currentSum); int diffClosest = Math.abs(target - closest); if (diffCurrent < diffClosest) { closest = currentSum; } else if (diffCurrent == diffClosest) { // 保持和为正数的顺序,避免不必要的重复 if (currentSum > closest) { closest = currentSum; } } // 根据当前和与目标的比较,移动指针 if (currentSum < target) { b++; } else { c--; } } } return closest; }}
这个代码首先对数组进行排序,然后使用双指针技巧来找到三个数的和与目标值最接近的情况。通过这种方法,我们能够高效地解决问题,避免了暴力枚举所有可能的三元组,显著提高了性能。
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2025年04月02日 19时01分28秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Kubernetes十三--Pod定义文件内容详解
2019-03-04
普歌- LRF-(简单易懂)笔记本电脑USB接口案例 接口多态(向下转型)
2019-03-04
Java中如何构建树结构
2019-03-04
解决eclipse字体背景变红或者变绿的问题
2019-03-04
扫雷小游戏——简单易懂
2019-03-04
软件架构-zookeeper快速入门
2019-03-04
「初级篇」跟我一起学docker(四)--容器的基本操作
2019-03-04
22 岁毕业做程序员的「普通」人,50 岁时的人生轨迹是怎样的?
2019-03-04
scala上界与下界、协变与逆变
2019-03-04
java稀疏数组
2019-03-04
全球数字货币加快研发
2019-03-04
数字化助力金融科技,实现产业良性循环
2019-03-04
2020-11-23(彻底理解KMP)
2019-03-04
angr学习笔记(7)(malloc地址单元符号化)
2019-03-04
windows环境利用start命令实现微信多开
2019-03-04
「CF149D」括号涂色 区间DP好题
2019-03-04
树状数组 模板总结
2019-03-04
「NOI2015」程序自动分析 并查集题解
2019-03-04
[JSOI2008]Blue Mary的战役地图 Hash题解
2019-03-04
结构型设计在工作中的一些经验总结
2019-03-04