LeetCode-16 最接近的三数之和
↑点击上面"算法半岛"
关注"算法半岛"第一时间接收最新文章
> 题目：16. 最接近的三数之和
> 难度：中等
> 分类：数组
> 解决方案：双指针
今天我们学习第16题最接近的三数之和，这是一道中等题。像这样数组的题目经常作为面试题来考察面试者算法能力和写代码能力，因此最好能手写出该题。下面我们看看这道题的题目描述。
题目描述
给定一个包括 n个整数的数组 nums和一个目标值 target。找出 nums中的三个整数，使得它们的和与 target最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：
给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).分析
这个题和LeetCode-15 三数之和的解题思路差不多，在第15题中是为了寻找满足 a+b+c=0，而在这道题中首先给出了一个目标值 target，然后寻找三个数 a+b+c的和与 target最接近，即 |a+b+c-target|的值最小。对示例分析如下图所示：
将上述分析过程转化为 java代码如下所示：
class Solution { public int threeSumClosest(int[] nums, int target) {
int sum =0; // 表示数组中三个元素的和 int dis = Integer.MAX_VALUE; // 表示数组中三个元素的和与target的距离，即|sum-target|
// 对数组进行排序 Arrays.sort(nums); // 遍历数组 for(int i=0; i<nums.length-2; ++i){ // 定义左指针和右指针 int left = i+1, right = nums.length-1;
while(left<right){ // 数组中三个元素的和与target的差，即sum-target int diff = nums[i] + nums[left] + nums[right] - target;
// 当sum-target == 0，则说明已经找到与target最近的数了（即target本身） if (diff == 0) return target;
// 寻找最小距离 if(Math.abs(diff) < dis){ dis = Math.abs(diff); sum = diff + target; }
// 移动左右指针 if(diff > 0){ --right; }else{ ++left; } } }
return sum; }}
Github地址
LeetCode-16 最接近的三数之和：https://github.com/JacobLei/leetcode/blob/master/src/main/java/A16_3SumClosest.java
参考链接
16. 最接近的三数之和：https://leetcode-cn.com/problems/3sum-closest/
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-05-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录