[leetcode题解] 16. 3Sum Closest

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

这个题目跟15题思路是相同的,只不过判断条件略有改变,另外题目要求返回sum,而不是返回组合,相比15题简单了一些。总体思路就是两数组中两指针问题。

代码如下:

int cmp(const void *pa, const void *pb)
{
    int a = *(int *)pa;
    int b = *(int *)pb;
    
    return a - b;
}

int threeSumClosest(int* nums, int numsSize, int target) {
    int sum = 0;
    int l = 0, r = numsSize - 1;
    int i = 0;
    int minx = INT_MAX;
    int res = 0;
    
    qsort(nums, numsSize, sizeof(int), cmp);
    for (i = 0; i < numsSize; i++) {
        l = i + 1;
        r = numsSize - 1;
        while (l < r) {
            sum = nums[i] + nums[l] + nums[r];
            if (abs(sum - target) < minx) {
                minx = abs(sum - target);
                res = sum;
            }
            
            if (sum < target)l++;
            else r--;
        }
    }
    return res;
}

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解] 16. 3Sum Closest

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/199.html

相关文章