#The way to brush questions with leetcode 16 - the closest sum of three numbers

Given an array of n integers nums and a target value target. Find three integers in nums so that their sum is closest to target. Returns the sum of the three numbers. Assume that there is only one answer for each group of input.

For example, given the array nums = [-1, 2, 1, - 4], and target = 1

The sum of the three numbers closest to target is 2. (- 1 + 2 + 1 = 2)

 

This question is very similar to the sum of the three numbers before:

Idea: still sort first, then traverse in turn. First, we need to know that in an increasing array, the later we traverse the sum of three numbers, the larger the sum of three numbers is. If the value of the sum of three numbers - target is greater than the current difference (positive number), then stop the loop immediately. If it is equal to target, it will return target directly.

 

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

Tags: C++

Posted on Tue, 03 Dec 2019 19:30:15 -0800 by bedted