LeetCode/16.cpp at master · changqing18/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

int threeSumClosest(vector<int> &nums, int target)
{
    int ans = 0, diff = INT_MAX;
    int size = nums.size();
    sort(nums.begin(), nums.begin() + size);

    for (int i = 0; i < size; i++)
    {
        int tmp = target - nums[i];
        int front = i + 1;
        int back = size - 1;
        while (front < back)
        {
            int sum = nums[front] + nums[back];
            if (sum < tmp)
            {
                front++;
                if (diff > tmp - sum)
                {
                    diff = tmp - sum;
                    ans = target - diff;
                }
            }
            else if (sum > tmp)
            {
                back--;
                if (diff > sum - tmp)
                {
                    diff = sum - tmp;
                    ans = diff + target;
                }
            }
            else
                return target;
        }
    }
    return ans;
}

int main()
{
    vector<int> nums(4, 1);
    printf("%d", threeSumClosest(nums, 0));
}