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

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C" active="active"]

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

[/restab]
[/restabs]

4.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C" active="active"]

#include 
#include 
#include 

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

[/restab]
[/restabs]

5. Submission Details

6. Runtime Distribution