题目描述

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

样例

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

算法1

(暴力枚举) O(n3)

三重循环枚举下标 i, j, k，然后判断 nums[i] + nums[j] + nums[k] 是否与 target 更接近。

时间复杂度

O(n3)

空间复杂度

仅需要常数的额外空间。

C 代码

int comp(const int* a, const int *b)
{
    return *(int*)a - *(int *)b;
}

int threeSumClosest(int* nums, int numsSize, int target){
    int ans = nums[0] + nums[1] + nums[2];
    for (int i = 0; i < numsSize; i ++ ) {
        for (int j = i + 1; j < numsSize; j ++ ) {
            for (int k = j + 1; k < numsSize; k ++ ) {
                if (abs(nums[i] + nums[j] + nums[k] - target) < abs(ans - target)) {
                    ans = nums[i] + nums[j] + nums[k];
                }
            }
        }
    }
    return ans;
}

算法2

(两重枚举) O(n2)

算法思想类似于3Sum。

首先将 nums 数组排序，然后固定一重循环枚举起始位置 i。
然后初始 l = i + 1，r = n - 1；如果发现 nums[i] + nums[l] + nums[r] == target，则可以直接返回 target；
若发现 nums[i] + nums[l] + nums[r] < target，则 l++；否则 r–；
直到 l>=r 停止，继续向后增加初始位置 i。

时间复杂度

排序的时间复杂度为 O(nlogn)。
共有 n个起始位置，然后每次循环 l 和 r 的时间复杂度为 O(n)。
故总时间复杂度为 O(n2)。

空间复杂度

仅需要常数的额外空间。

C 代码

int comp(const int* a, const int *b)
{
    return *(int*)a - *(int*)b;
}

int threeSumClosest(int* nums, int numsSize, int target){
    int ans = nums[0] + nums[1] + nums[2];

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

    for (int i = 0; i < numsSize; i ++ ) {
        int l = i + 1, r = numsSize - 1;

        while (l < r) {
            if (abs(nums[i] + nums[l] + nums[r] - target) < abs(ans - target)) {
                ans = nums[i] + nums[l] + nums[r];
            }

            if (nums[i] + nums[l] + nums[r] == target) {
                return target;
            }
            else if (nums[i] + nums[l] + nums[r] < target) {
                l ++ ;
            }
            else {
                r -- ;
            }
        }        
    }
    return ans;
}