每周一道算法题(十二)

上周还在郁闷自己写的算法由于超时没有通过，这周就给了一个弥补的机会，难度级别“Medium”

题目：已知n个整数的数组nums，给定一个数target。数组S中任意三个数求和，找到其中最接近target的值。保证每个输入都对应单一解。

通过上周的题再来看这道题,就很简单了，直接代码解说吧：

int threeSumClosest(int* nums, int numsSize, int target) {
    //如果给出的数组个数少于3个,就不用比了
    if (numsSize == 0) return 0;
    if (numsSize == 1) return nums[0];
    if (numsSize == 2) return nums[0] + nums[1];
    //数据初始化,初始化的结果是前三个数字的和
    int result = nums[0] + nums[1] + nums[2];
    int temp = abs(result - target);
    int i,j,k;
    //上周我的笨算法，把所有的组合全部查一遍，找出符合要求的结果
    for (i = 0; i < numsSize; i++) 
        for (j = i+1; j < numsSize; j++) {
            if (j == i) continue;
            for (k = j+1; k < numsSize; k++) {
                if (k == i || k == j) continue;
                if (nums[i] + nums[j] + nums[k] == target) return target;
                //通过比较绝对值来找出最贴近target的数
                if (abs(nums[i] + nums[j] + nums[k] - target) < temp) {
                    result = nums[i] + nums[j] + nums[k];
                    temp = abs(result - target);
                }
            }
        }
    //返回结果
    return result;
}

虽然这次的算法通过了，但是效率还是比较低的，可以通过上周的思路，先排序，然后从两边开始找就OK了。。。

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!