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月前
杨氏矩阵( 时间复杂度要求小于O(N) )
有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编写程序在这样的矩阵中查找某个数字是否存在,且程序的时间复杂度要小于O(N);
|
3月前
|
算法
LeetCode第16题最接近的三数之和
该文章介绍了 LeetCode 第 16 题最接近的三数之和的解法,与第 15 题类似,通过双指针法减少循环次数,根据差值的绝对值来更新最接近的和,并总结了双指针可减少循环次数的要点。
|
3月前
|
算法 Java
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
40 0
|
6月前
16. 最接近的三数之和
16. 最接近的三数之和
34 1
|
6月前
|
算法 测试技术 C#
【折半处理 二分查找】1755. 最接近目标值的子序列和
【折半处理 二分查找】1755. 最接近目标值的子序列和
【折半处理 二分查找】1755. 最接近目标值的子序列和
|
6月前
16.最接近的三数之和
16.最接近的三数之和
31 0
|
6月前
|
人工智能 算法
前缀和算法题(区间次方和、小蓝平衡和、大石头的搬运工、最大数组和)
前缀和算法题(区间次方和、小蓝平衡和、大石头的搬运工、最大数组和)
|
6月前
|
算法 C++ 索引
寻找最接近子数组和的算法设计及其C++实现
寻找最接近子数组和的算法设计及其C++实现
40 4
|
6月前
|
搜索推荐
【hoare优化版】快速排序算法 | 三数取中&小区间优化(2)
【hoare优化版】快速排序算法 | 三数取中&小区间优化(2)
75 0
|
6月前
leetcode-16:最接近的三数之和
leetcode-16:最接近的三数之和
47 0