欢迎来到军工软件开发人才培养基地——学到牛牛

最接近的三数之和

时间:2024-05-06 07:01:10 来源:学到牛牛

​题目描述:

给你一个长度为 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

 

解题思路:

三数之和和两数之和思路大致相同,本题目因为要计算三个数,如果靠暴力枚举的话时间复杂度会到 O(n3),需要降低时间复杂度。

首先对数组进行排序,在数组nums中进行遍历,每遍历一个值利用其下标i,形成一个固定值 nums[i],再使用左指针指向 left = i + 1 处,右指针指向 right = nums.length - 1 处,也就是结尾处根据 temp = nums[i] +nums[left] + nums[right] 的结果,判断 temp 与目标 target 的距离,如果更近则更新结果同时判断 temp 与 target 的大小关系,因为数组有序,如果temp> target 则 right--,如果 temp < target 则 left++,如果 temp == target 则说明距离为 0 直接返回结果。整个遍历过程,固定值为 n 次,双指针为 n 次,时间复杂度为 O(n 2)

  

完整代码:

int cmp(const void* a,const void* b){

    return *(int*)a - *(int*)b;

}

int threeSumClosest(int* nums, int numsSize, int target){

    int temp = 0,best = 200000000;

    /*整数数组排序*/

    qsort(nums,numsSize,sizeof(int),cmp);

    for(int i = 0;i<numsSize;i++){

        /*跳过重复元素*/

        if(i > 0 && nums[i] == nums[i-1]){

            continue;

        }

        /*确定左右指针*/        

        int left = i+1, right = numsSize-1;

        /*遍历一下*/

        while(left < right){

             temp = nums[i] + nums[left] + nums[right];\

             /*等于直接输出*/

             if(temp == target)

             return target;

             /*值小于目标值,则左指针右移,否则右指针左移*/

             if(temp - target < 0)

             left++;

             else right--;

             /*求与target最接近的值,即diff = temp-target的绝对值最小即最接近*/

             if((abs)(temp - target) < (abs)(best - target))

{

              best = temp;

             }else{

  continue;

}

        }

    }

        return  best;

}