1. Description

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

2. Example

given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

3. Code

static int compare(const void* a, const void *b) {
    return *(int*)a - *(int*)b;
}

int threeSumClosest(int* nums, int numsSize, int target) {

    qsort(nums, numsSize, sizeof(int), compare);

    int result = 0, min = INT_MAX;

    for (int i = 0; i < numsSize - 2; i++)
    {
        if (i > 0 && nums[i] == nums[i - 1])
        {
            continue;
        }

        int head = i + 1, tail = numsSize - 1;

        while (head < tail)
        {
            int tmp = nums[head] + nums[tail] + nums[i];

            if (min > abs(tmp - target)) {
                min = abs(tmp - target);
                result = tmp;
            }

            if (tmp > target) {
                tail--;
            }
            else if(tmp < target){
                head++;
            }
            else {
                return tmp;
            }
        }
    }
    return result;
}

4.Test

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

static int compare(const void* a, const void *b) {
    return *(int*)a - *(int*)b;
}

int threeSumClosest(int* nums, int numsSize, int target) {

    qsort(nums, numsSize, sizeof(int), compare);

    int result = 0, min = INT_MAX;

    for (int i = 0; i < numsSize - 2; i++)
    {
        if (i > 0 && nums[i] == nums[i - 1])
        {
            continue;
        }

        int head = i + 1, tail = numsSize - 1;

        while (head < tail)
        {
            int tmp = nums[head] + nums[tail] + nums[i];

            if (min > abs(tmp - target)) {
                min = abs(tmp - target);
                result = tmp;
            }

            if (tmp > target) {
                tail--;
            }
            else if(tmp < target){
                head++;
            }
            else {
                return tmp;
            }
        }
    }
    return result;
}

int main()
{
    int arr[] = { 1,1,1,0 };
    printf("%d\n", threeSumClosest(arr, 4, -100));
    system("pause");
    return 0;
}

5. Submission Details

6. Runtime Distribution