1. 代码段小站首页
  2. 算法

leetcode16-最接近的三数之和

彭晨涛 • • 算法 • 阅读 7

原题

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

解法

思想

和leetcode15-三数之和的解法相近，确定一个指针后，使用剩下的两个指针逼近目标数。在移动过程中计算与目标数的最小绝对值差值。

代码

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for(int i=0;i<nums.length-2;i++) {
            int start = i+1, end = nums.length - 1;
            while(start < end) {
                int sum = nums[start] + nums[end] + nums[i];
                if(Math.abs(target - sum) < Math.abs(target - ans))
                    ans = sum;
                if(sum > target) end--;
                else if(sum < target) start++;
                else return ans;
            }
        }
        return ans;
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode16-%e6%9c%80%e6%8e%a5%e8%bf%91%e7%9a%84%e4%b8%89%e6%95%b0%e4%b9%8b%e5%92%8c/

赞 (0)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年5月4日 16:46
下一篇 2020年5月5日 16:52

相关推荐

  • leetcode131-分割回文串

    原题 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: "aab" 输出: [ ["aa","b"], ...

    彭晨涛 彭晨涛
    算法 2020年5月22日
    080

  • leetcode695-岛屿的最大面积

    原题 给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围...

    彭晨涛 彭晨涛
    算法 2020年3月15日
    01220

  • leetcode56-合并区间

    原题 给出一个区间的集合，请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]]...

    彭晨涛 彭晨涛
    算法 2020年4月16日
    0150

  • leetcode76-最小覆盖子串

    原题 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。 示例: 输入: S = "ADOBECODEBANC", T = "ABC" 输...

    彭晨涛 彭晨涛
    算法 2020年5月23日
    0140

  • 剑指offer59-队列的最大值

    原题（来源Leetcode） 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的时间复杂度...

    彭晨涛 彭晨涛
    算法 2020年3月7日
    0120

  • leetcode77-组合

    原题 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [...

    彭晨涛 彭晨涛
    算法 2020年5月12日
    0370

  • leetcode123-买卖股票的最佳时机III

    原题 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易（你...

    彭晨涛 彭晨涛
    算法 2020年6月16日
    01200

  • leetcode503-下一个更大元素II

    原题 给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，...

    彭晨涛 彭晨涛
    算法 2020年2月1日
    090

  • 蓝桥杯试题-黑色星期五

    原题 资源限制 时间限制：1.0s 内存限制：512.0MB 问题描述　　有些西方人比较迷信，如果某个月的13号正好是星期五，他们就会觉得不太吉利，用古人的说法，就是“诸事不宜”。...

    彭晨涛 彭晨涛
    算法 2020年2月28日
    0100
  • leetcode206-反转链表 算法

    leetcode206-反转链表

    原题 反转一个单链表。 示例： 输入： 1->2->3->4->5->NULL 输出： 5->4->3->2->1->NULL 进阶： 你可以迭代或递归地反转链表。你能否用两种方法...

    彭晨涛 彭晨涛
    2019年12月16日
    090

发表回复

登录后才能评论