《leetCode》：3Sum Closest

本文主要是介绍《leetCode》：3Sum Closest，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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

思路

由于上篇博文：3Sum中利用暴力搜索法能够AC，这个题，我也尝试用暴力搜索法做了下，代码如下：

int threeSumClosest(int* nums, int numsSize, int target) {if(nums==NULL||numsSize<4){//有效性检查return 0;}//还是用暴力搜索法来做int close=2147483647;int temp=0;int index1,index2,index3;for(int i=0;i<numsSize-2;i++){for(int j=i+1;j<numsSize-1;j++){for(int k=j+1;k<numsSize;k++){temp=nums[i]+nums[j]+nums[k];int tempClose=abs(target-temp);if(tempClose<close){close=tempClose;index1=i;index2=j;index3=k;}}}}return nums[index1]+nums[index2]+nums[index3];}

可惜，这种方法在这里是行不通的，运行超时。
结果如图：

这样的题才是好题，因为考查的就是我们的算法，如果这样就AC了，相信我们都不会继续往下面研究，我自己也是这样一个德行。
只有这样，我们才会不得不继续思考，研究，找出好的算法来减少时间复杂度。

思路二

第一步：先对数组进行排序
第二步：将3Sum转化为2Sum进行求解。即通过一个循环来固定第一个数a,然后在剩余的数中寻找b 、c使得b+c更加接近于target-a的值。

实现代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int cmp(const void *a,const void *b){return ( (*((int *)a))- (*((int *)b)));
}int threeSumClosest(int* nums, int numsSize, int target) {if(nums==NULL||numsSize<3){//有效性检查return 0;}//先对nums进行排序，然后借助于在sorted  array 中求2Sum的方法进行求解int min_dif=INT_MAX;qsort(nums,numsSize,sizeof(nums[0]),cmp); for(int i=0;i<numsSize;i++){int begin=i+1;int end=numsSize-1;while(begin<end){//借助于2Sum的方法int dif=nums[i]+nums[begin]+nums[end]-target;if(dif==0){//找到精确的组合return target; } else{if(abs(dif)<abs(min_dif)){min_dif=dif;}//通过dif的符号在改变begin和end，使结果更加逼近与target if(dif<0){//increase valuebegin++;}else{//decrease valueend--;}}}}return min_dif+target; }int main(void){int k;int target;while(scanf("%d  %d",&k,&target)!=EOF&&k>=3){int *nums=(int *)malloc(k*sizeof(int));for(int i=0;i<k;i++){scanf("%d",nums+i);}int result=threeSumClosest(nums,k,target);printf("%d\n",result);}
}

AC结果如下：

这篇关于《leetCode》：3Sum Closest的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---