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]
Comments | NOTHING