题目描述

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

样例

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

算法1

时间复杂度 $O(n^2)$

排序O(nlogn)
枚举O(n^2)

排序后i从0开始遍历, l=i+1, r=n-1；
计算 nums[i] + nums[l] + nums[r] 更新结果；
枚举 i , l , r 时循环去重。

Java 代码

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int n=nums.length;
        Arrays.sort(nums);
        int ans=0x3f3f3f3f;
        for(int i=0;i<n;i++){
            while(i!=0&&i<n&&nums[i]==nums[i-1])
                i++;
            int l=i+1,r=n-1;
            while(l<r){
                int val=nums[i]+nums[l]+nums[r];
                if(val==target)
                    return target;
                else if(val<target){
                    ans=(Math.abs(target-val)<Math.abs(ans-target))?val:ans;
                    do{l++;}while(l<r&&nums[l]==nums[l-1]);
                }else if(val>target){
                    ans=(Math.abs(target-val)<Math.abs(ans-target))?val:ans;
                    do{r--;}while(l<r&&nums[r]==nums[r+1]);
                }
            }
        }
        return ans;
    }
}