leetcode-0016

题目：

最接近的三数之和

关键词：
排序 二分法查找

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

static int CmpMajor(const void *num1, const void *num2)
{
    return *(int *)num2 - *(int *)num1;
}

static int CmpMinor(const void *num1, const void *num2)
{
    return *(int *)num1 - *(int *)num2;
}

static int binSearch(const int *array, int size, int target, int *result)
{
    if ((result == NULL) || (array == NULL) || (size <= 0)) {
        return -1;
    }
    if (size == 1) {
        *result = array[0];
        return 0;
    }
    int offset = size / 2;
    if (target == array[offset]) {
        *result = array[offset];
        return 0;
    } else if (offset == 1) {
        if (abs(target - array[0]) > abs(target - array[1])) {
            if (size == 3) {
                *result = (abs(target - array[1]) < abs(target - array[2])) ? array[1] : array[2];
            } else {
                *result = array[1];
            }
        } else {
            *result = array[0];
        }
        return 0;
    } else if (target < array[offset]) {
        return binSearch(array, size - offset, target, result);
    } else {
        return binSearch(&array[offset], size - offset, target, result);
    }
}

int threeSumClosest(int* nums, int numsSize, int target)
{
    if ((nums == NULL) || (numsSize < 3)) {
        printf("invalid args\n");
        return -1;
    }
    qsort(nums, numsSize, sizeof(int), CmpMinor);
    int i, j;
    for (i = 0; i < numsSize; i++) {
        printf("%d ", nums[i]);
    }
    printf("\n");
    int closest = 0;
    for (i = 0; i < numsSize - 2; i++) {
        for (j = i + 1; j < numsSize - 1; j++) {
            int minus = target - nums[i] - nums[j];
            int result;
            int ret = binSearch(&nums[j + 1], numsSize - j - 1, minus, &result);
            if (ret != 0) {
                continue;
            }
            int tmp = nums[i] + nums[j] + result;
            if (tmp == target) {
                return target;
            }
            if (j == 1) {
                closest = tmp;
                continue;
            }
            // printf("nums[i]%d, nums[j]=%d, result=%d, minus=%d\n", nums[i], nums[j], result, minus);
            // printf("closest=%d, tmp=%d, target=%d\n", closest, tmp, target);
            if (abs(tmp - target) < abs(closest - target)) {
                closest = tmp;
            }
        }
    }
    return closest;
}