16、最近的三数之和

leetcode

Created At : 2020-07-26 00:19

Count:231 Views 👀 :

16、最近的三数之和
1. 示例：
题解
1. 1、排序 + 双指针

16、最近的三数之和

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

示例：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示：

3 <= nums.length <= 10^3
10^3 <= nums[i] <= 10^3
10^4 <= target <= 10^4

链接：https://leetcode-cn.com/problems/3sum-closest

题解

1、排序 + 双指针

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

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com