leetcode 16. 最接近的三数之和(3Sum Closest)

佚名 6年前 (2019-04-10) 随笔 1183人围观抢沙发百度已收录

题目描述：

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

示例：

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

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

解法：

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int sz = nums.size();
        if(sz < 3){
            return -1;
        }else{
            sort(nums.begin(), nums.end());
            int res = nums[0] + nums[1] + nums[2];
            for(int i = 0; i < sz; i++){
                int l = i+1;
                int r = sz - 1;
                while(l < r){
                    int val = nums[i] + nums[l] + nums[r];
                    if(val == target){
                        return target;
                    }else if(val < target){
                        l++;
                        while(l < r && nums[l] == nums[l-1]){
                            l++;
                        }
                        if(abs(res - target) > target - val){
                            res = val;
                        }
                    }else{
                        r--;
                        while(l < r && nums[r] == nums[r+1]){
                            r--;
                        }
                        if(abs(res - target) > val - target){
                            res = val;
                        }
                    }
                }
            }
            return res;
        }
    }
};