title: 算法小练——最接近的三数之和
categories:

• Algorithms
  tags:
• medium
  abbrlink: 1687200905
  date: 2019-12-02 20:43:54

最接近的三数之和

描述

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

举例

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

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

代码

 public int threeSumClosest(int[] nums, int target) {

        int max_int = Integer.MAX_VALUE;
        int ans = 0;
        for (int i = 0; i < nums.length-2; i++) {
            for (int j = 1; j < nums.length-1; j++) {
                for (int k = 2; k < nums.length; k++) {
                    if(i<j && j<k){
                        int c = nums[i]+nums[j]+nums[k];
                        int min = Math.max(target,c)-Math.min(target,c);
                        if(min<max_int){
                            max_int = min;
                            ans = c;
                        }

                    }
                }
            }
        }
        return ans;
    }

代码优化

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;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;
    }
}

作者：guanpengchn
链接：https://leetcode-cn.com/problems/3sum-closest/solution/hua-jie-suan-fa-16-zui-jie-jin-de-san-shu-zhi-he-b/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。