LeetCode 16 最接近的三数之和（C语言 双指针法）

LeetCode 16 最接近的三数之和（C语言 双指针法）

题目：

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在恰好一个解。

示例1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例2：

输入：nums = [0,0,0], target = 1
输出：0

提示：

3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
- 1 0 4 10^4 104 <= target <= 1 0 4 10^4 104

解题代码：

int cmp(const void *x,const void *y){
    return *(int*)x - *(int*)y;
}

int threeSumClosest(int* nums, int numsSize, int target){
	// 小于3直接返回空
    if(numsSize < 3)
        return NULL;
    // 等于3直接返回三数之和
    if(numsSize == 3)
        return nums[0] + nums[1] + nums[2];
    // 快速排序
    qsort(nums,numsSize,sizeof(int),cmp);
    // 记录最接近target的三数和
    int ret = 0x7FFFFFFF;
    // 记录和离target最近的距离
    int minSqrt = 0x7FFFFFFF;
    for(int i = 0; i < numsSize - 2; i++){
        if(i > 0 && nums[i] == nums[i -1])
            continue;
        int left = i + 1;
        int right = numsSize - 1;
        while(left < right){
        	// 记录三数之和
            int sum = nums[i] + nums[left] + nums[right];
            // 记录sum到target的距离
            int sqrt = 0;
            // 相等直接返回
            if(sum == target)
                return sum;
            else if(sum > target){
                sqrt = sum - target;
                // 大于sqrt说明右边界太大了 right--
                right--;
            }else {
                sqrt = target - sum;
                // 小于sqrt说明左边界太大了 left++
                left++;
            }
            if(minSqrt > sqrt){
            	// 记录最小的距离
                minSqrt = sqrt;
                // 记录最小距离所对应的和 也就是要返回的值
                ret = sum;
            }
        }
    }
    return ret;
}

和 LeetCode 15 三数之和 思路一样