leetcode16最接近的三数之和 （排序+ 双指针）

​
​

作者简介：C/C++ 、Golang 领域耕耘者，创作者
个人主页：作者主页
活动地址：CSDN21天学习挑战赛
如果感觉博主的文章还不错的话，还请关注➕ 、点赞👍 、收藏🧡三连支持一下博主哦~~~

💜 题目描述

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例1：

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

示例2：

输入：nums = [0,0,0], target = 1
输出：0

🧡 算法分析

此题用到了排序+ 双指针的思想

具体算法步骤为：

1. 直接排序整个数组，然后从头开始遍历每个数，此时第一个数已经确定
2. 用双指针l，r分别从左边l = i + 1和右边n - 1往中间靠拢，找到sum = nums[i] + nums[l] + nums[r]所有情况中最接近target的sum，更新re
3. 在双指针移动的过程中，三数之和假设为sum
   • 若sum > target，则r往左走，使sum变小，更接近target
   • 若sum < target，则l往右走，使sum变大，更接近target
   • 若sum == target，则表示找到了与num[i]搭配的组合num[l]和num[r]，直接返回

💚 代码实现

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        pair<int, int> re(INT_MAX, INT_MAX);
        for(int i = 0; i< nums.size(); i++)
        {
            for(int j = i + 1, k = nums.size() - 1; j < k; j++)
            {
                while(k - 1 > j && nums[i] + nums[j] + nums[k - 1] >= target) k --;
                int s = nums[i] + nums[j] + nums[k];
                re = min(re, make_pair(abs(s - target), s));  // re中存取的是 差值 ，三数之和
                if( k - 1 > j)
                {
                    s = nums[i] + nums[j] + nums[k - 1];   // 找到前面一个
                    re = min(re, make_pair(abs(target - s), s));
                } 
            }
        }
         return re.second;
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

执行结果：

💙 时间复杂度分析

其中遍历了两种循环， 时间复杂度为O(n²)

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
🧡 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！