首页 > itarticle > PU 3Sum Closest

PU 3Sum Closest

admin 11月 12, 2020 0

Jan 01, 1970

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.

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).

C Solution:

void quick_sort(int *nums, int numsSize) {
    if (numsSize < 2) return;
    int key = nums[numsSize - 1];
    int i;
    for (i = 0; i < numsSize - 1 && nums[i] < key; i++);
    if (i == numsSize - 1) {
        quick_sort(nums, numsSize - 1);
        return;
    }
    int j;
    for (j = i + 1; j < numsSize - 1; j++) {
        if (nums[j] < key) {
            int tmp = nums[j];
            nums[j] = nums[i];
            nums[i++] = tmp;
        }
    }
    nums[numsSize - 1] = nums[i];
    nums[i] = key;
    quick_sort(nums, i);
    quick_sort(nums + i + 1, numsSize - i - 1);
}
void twoSumClosest(int *nums, int numsSize, int target, int *bigger, int *smaller) {
    int l, r;
    for (l = 0, r = numsSize - 1; l < r;) {
        if (nums[l] + nums[r] == target) {
            *bigger = *smaller = 0;
            return;
        }
        if (nums[l] + nums[r] > target) {
            int tmp = nums[l] + nums[r] - target;
            if (*bigger > tmp) *bigger = tmp;
            r--;
        }
        else {
            int tmp = target - nums[l] - nums[r];
            if (*smaller > tmp) *smaller = tmp;
            l++;
        }
    }
}
int threeSumClosest(int* nums, int numsSize, int target) {
    quick_sort(nums, numsSize);
    int i, bigger = INT_MAX, smaller = INT_MAX;
    for (i = 0; i < numsSize - 2; ) {
        twoSumClosest(nums + i + 1, numsSize - i - 1, target - nums[i], &bigger, &smaller);
        if (bigger == 0) return target;
        for (i++; i < numsSize - 2 && nums[i - 1] == nums[i]; i++);
    }
    if (bigger > smaller) return target - smaller;
    return target + bigger;
}

Summary:

Quite similar to threeSum.
'closest' maybe either bigger or smaller.
6ms(beats 64.71%), rarely 3ms(beats 96.08%).

LeetCode: 16. 3Sum Closest