首页 > 代码库 > 3sum closest

3sum closest

2024-08-22 07:02:43   222人阅读

　　问题描述：

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).
由此我们可以知道，该算法的目的是求出3个数的和与目标值最相近解。与就3sum的算法类似，为了降低时间复杂度，我们需要先对数组进行排序，然后在对每次选择的3个数据之和进行判断，
与3sum不同的是，3sum将和与0进行比较，而3sum closest是将和与目标值进行比较。每次比较分3次情况：
1 sum==target 此时表明3个数据的sum与target最近，不用继续后续操作，直接返回。
2 sum>target 此时应当高位坐标进行减一操作，并且记录下来sum与target之间的差距，判断新差距与旧差距的大小，并且更新差距diff
3 sum<target 此时应当低位坐标进行加1 操作，同样更新差距diff
具体代码如下：
技术分享 
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
void QSort(int *nums,int low,int high){
    int i=low;
    int j=high;
    if(i>=j)return ;
    int key=nums[i];
    while(i<j){
        while(i<j&&nums[j]>key)j--;
        nums[i]=nums[j];
        while(i<j&&nums[i]<=key)i++;
        nums[j]=nums[i];
    }
    nums[i]=key;
    QSort(nums,low,i-1);
    QSort(nums,i+1,high);
}
int threeSumClosest(int* nums, int numsSize, int target) {
    if(numsSize<3)return 0;
    int sum;
    int diff=abs(target-(nums[0]+nums[1]+nums[2]));
    int res=nums[0]+nums[1]+nums[2];
    int low;
    int high;
    QSort(nums,0,numsSize-1);
    for(int i=0;i<numsSize;i++)printf("%d ",nums[i]);
    for(int i=0;i<numsSize-2;i++){
        if(i>0&&nums[i]==nums[i-1])continue ;
        low=i+1;
        high=numsSize-1;
        while(low<high){
            sum=nums[i]+nums[low]+nums[high];
            if(abs(target-sum)<diff){
                diff=abs(target-sum);
                res=sum;
            }
            if(sum<target){
                low++;
            }
            else if(sum>target){
                high--;
            }else return sum;
        }
    }
    return res;    
}
View Code

 



3sum closest


联系
我们