LeetCode 16.3Sum Closest (最接近的三数之和)

青旅半醒 2022-05-11 00:26 244阅读 0赞

题目描述：

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

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

Accepted C++ Solution:

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        vector<int> v(nums.begin(),nums.end());
        int n = 0;
        int ans = 0;
        int sum;
        sort(v.begin(),v.end());        //有序
        while(v.size() <= 3)
            return accumulate(v.begin(),v.end(),0);
        n = v.size();
        ans = v[0] + v[1] + v[2];
        for (int i = 0; i < n-2 ; i++) {
            int j = i+1;                //后一个    
            int k = n-1;                //最后一个
            while(j<k) {
                sum = v[i] + v[j] + v[k];
                if (abs(target-sum) < abs(target-ans)) {
                    ans = sum;
                    if (ans == target)  return  ans;
                }
                (sum > target) ? k-- : j++;
            }
        }
        return ans;
    }
};