精选50题之 16. 最接近的三数之和

骑猪看日落 2024-04-17 23:37 64阅读 0赞

### 腾讯精选练习（50 题）之 16. 最接近的三数之和 ###

*   *  原题目链接
     *  题目分析
     *  解题思路
     *  代码实现
     *  写在最后

## [原题目链接][Link 1] ##

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

> 例如，给定数组 nums = \[-1，2，1，-4\], 和 target = 1.  
> 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

## 题目分析 ##

刚完成的 [精选50题之 15. 三数之和][50_ 15.] 和这道题的背景，数据结构，输入一致，仅是在判定上有区别。所以可以相同的思路进行求解，即双指针法。

## 解题思路 ##

相对于 [精选50题之 15. 三数之和][50_ 15.]，需要增加绝对值的判断，而循环中的判断条件有所调整、删减。整体上变化不大。

## 代码实现 ##

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

运行结果，很不错。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]

## 写在最后 ##

遇到做过的题，熟悉的思路可以解决迅速解决问题，感觉很不错?

[Link 1]: https://leetcode-cn.com/problems/3sum-closest/
[50_ 15.]: https://blog.csdn.net/weixin_41728431/article/details/100187983
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/c2e86f76cda14e039eb7c76605867dab.png