leetcode16 Sum of the closest three numbers (sort + double pointer)

​
​

作者简介：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

🧡 算法分析

Sorting is used in this question+ 双指针的思想

具体算法步骤为：

1. Sort the entire array directly,Then iterate over each number from the beginning,At this point the first number has been determined
2. 用双指针l,r分别从左边l = i + 1和右边n - 1往中间靠拢,找到sum = nums[i] + nums[l] + nums[r]closest of alltarget的sum,更新re
3. During the movement of the double pointer,The sum of the three numbers is assumed to be sum
   • 若sum > target,则r往左走,使sum变小,更接近target
   • 若sum < target,则l往右走,使sum变大,更接近target
   • 若sum == target,Indicates that and is foundnum[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];   // find the previous one
                    re = min(re, make_pair(abs(target - s), s));
                } 
            }
        }
         return re.second;
    }

};

执行结果：

时间复杂度分析

Two kinds of loops are traversed, 时间复杂度为O(n²)

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