[数据结构与算法]每日LeetCode一道题————最接近的三数之和

每日一题

题目说明

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

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

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/3sum-closest/solution/zui-jie-jin-de-san-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处

算法思路

排序+双指针：
和LeetCode第15题——三数之和思路类似，多加个判断条件基本就完成了。
详细思路可以参考 每日LeetCode一道题——三数之和
其中，abs()函数是取绝对值函数

代码实现

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target)
    {
        int n = nums.size();
        int sum = 0;
        int best = 1e6;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; i++)
        {
            if (i > 0 && nums[i] == nums[i - 1])
            {
                continue;
            }
            int k = n - 1;
            int j = i + 1;
            while ( j < k)
            {
                sum = nums[i] + nums[j] + nums[k];
                if (sum > target) 
                {
                    k--;
                }
                else if (sum == target)
                {
                    return target;
                }
                else
                {
                    j++;
                }
                if (abs(sum - target) < abs(best - target))
                {
                    best = sum;
                }
            }
        }
        return best;
    }
};

复杂度分析

• 时间复杂度：O(N ^ 2)，其中 NN 是数组 nums 的长度。我们首先需要 O(NlogN) 的时间对数组进行排序，随后在枚举的过程中，使用一重循环 O(N) 枚举 a，双指针 O(N)枚举 b 和 c，故一共是 O(N^2)。

• 空间复杂度：O(logN)。排序需要使用 O(logN) 的空间。然而我们修改了输入的数组 nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序，此时空间复杂度为 O(N)。