首页 > > 程序设计 > C/C++ >

#leetcode刷题之路16-最接近的三数之和

2019-03-12 08:23:02来源：博客园阅读 ()

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

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

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

这个题和之前的的三数之和有非常相近之处：

思路：依然是先排序，然后依次遍历。这里加上点约束来优化，首先是我们要知道，在递增的数组中，越往后遍历三数之和越大，如果（三数之和-target）的值大于当前的差值（正数），那么立刻停止循环。如果等于target则直接返回target。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int threeSumClosest(vector<int>& nums, int target)
{
    int len = nums.size();
    int dif = INT_MAX;
    int ans = target;
    sort(nums.begin(), nums.end());
    for (int i = 0; i<len - 2; i++)
    {
        for (int j = i + 1; j<len - 1; j++)
        {
            for (int k = j + 1; k<len; k++)
            {
                //cout << nums[i] << " " << nums[j] << " " << nums[k];
                int tdif = (nums[i] + nums[j] + nums[k]) - target;
                if (tdif == 0) return target;
                if (abs(tdif)<dif)
                {
                    dif = abs(tdif);
                    ans = nums[i] + nums[j] + nums[k];
                }
                //cout << " " <<ans<<endl;
                if (tdif> dif) break;
            }
        }
    }
    return ans;
}

int main() {
    vector<int> a = { 1, 2, 4, 8, 16, 32, 64, 128};
    int target=82;
    int ans=threeSumClosest(a,target);
    std::cout << ans << std::endl;
    return 0;
}