16. 最接近的三数之和

简介: 16. 最接近的三数之和

找到三数之和与target最接近,返回这三个数的和。假设答案唯一。

分析:与15.三数之和类似https://pigeon.blog.csdn.net/article/details/115711407,

同样采用 排序+双指针 方法。

    public int threeSumClosest(int[] nums, int target) {
        int ans = nums[0]+nums[1]+nums[2];
        int closest = Math.abs( ans - target);
        Arrays.sort(nums);
        int n  = nums.length;
        //枚举a
        for (int first = 0; first < n; first++) {
            //twoSum
            int third = n-1;
            for (int second = first+1; second < n; second++) {
               while (second < third && (nums[first]+nums[second]+nums[third] - target)>0 ){
                   third--;
               }
               if (second == third) {
                   if (second+1<n && Math.abs(nums[first]+nums[second]+nums[second+1]-target)<closest ) {
                       ans = nums[first]+nums[second]+nums[second+1];
                       closest = Math.abs(ans-target);
                   }
               }
               else  {
                   if (Math.abs(nums[first]+nums[second]+nums[third]-target)<closest) {
                        ans = nums[first] + nums[second] + nums[third];
                        closest = Math.abs(ans-target);
                       }
                   if (third+1<n && Math.abs(nums[first]+nums[second]+nums[third+1]-target)<closest) {
                         ans = nums[first] + nums[second] + nums[third+1];
                         closest = Math.abs(ans-target);
                       }
                   }
            }
 
        }
        return ans;
 
    }
相关文章
|
6月前
|
算法 测试技术 C#
【贪心】【分类讨论】2499. 让数组不相等的最小总代价
【贪心】【分类讨论】2499. 让数组不相等的最小总代价
|
3月前
|
算法
LeetCode第16题最接近的三数之和
该文章介绍了 LeetCode 第 16 题最接近的三数之和的解法,与第 15 题类似,通过双指针法减少循环次数,根据差值的绝对值来更新最接近的和,并总结了双指针可减少循环次数的要点。
|
6月前
16. 最接近的三数之和
16. 最接近的三数之和
34 1
|
6月前
|
算法 测试技术 C#
【折半处理 二分查找】1755. 最接近目标值的子序列和
【折半处理 二分查找】1755. 最接近目标值的子序列和
【折半处理 二分查找】1755. 最接近目标值的子序列和
|
6月前
16.最接近的三数之和
16.最接近的三数之和
31 0
|
6月前
|
算法 C++ 索引
寻找最接近子数组和的算法设计及其C++实现
寻找最接近子数组和的算法设计及其C++实现
41 4
|
6月前
|
搜索推荐
【hoare优化版】快速排序算法 | 三数取中&小区间优化(2)
【hoare优化版】快速排序算法 | 三数取中&小区间优化(2)
77 0
|
6月前
leetcode-16:最接近的三数之和
leetcode-16:最接近的三数之和
50 0
|
Java
简单计算时间复杂度
简单计算时间复杂度
35 1
|
11月前
|
机器学习/深度学习 算法 测试技术
C++二分算法: 找出第 K 小的数对距离
C++二分算法: 找出第 K 小的数对距离