leetcode 16. 最接近的三数之和（C++）

蔚落 2023-07-11 08:49 16阅读 0赞

p.s python版——>[leetcode 16：最接近的三数之和(python)][leetcode 16_python]

# 题目 #

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

例如，给定数组 nums = \[-1，2，1，-4\], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

来源：[16. 最接近的三数之和 - 力扣（LeetCode）][16. _ - _LeetCode]  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

# 暴力法 #

*  直接做三层循环，逐一遍历，寻找最接近的值输出  
    因为不要求找出是哪几个数相加，所以当sum等于target时，直接返回target

代码如下：

class Solution { 
    public:
        int threeSumClosest(vector<int>& nums, int target) { 
            int len = nums.size();
            int res = 10000;
            int p1 = 0;
            while(p1<len-2)
            {     
                int p2 = p1 + 1;
                while(p2 < len - 1)
                {     
                    int p3 = p2 + 1;
                    while(p3 < len)
                    {     
                        int newsum = nums[p1] + nums[p2] + nums[p3];
                        if(abs(newsum-target) < abs(res-target))
                        {     
                            res = newsum;
                            if (res == target)
                                return target;
                        }
                        p3++;
                    }
                    p2++;
                }
                p1++;
            }
            return res;
        }
    };

结果：  
![在这里插入图片描述][20200304222048201.png]

# 定一移二法 #

*  利用前一题 [leetcode 15. 三数之和][leetcode 15.] 的框架  
    双指针+重复的数跳过

代码如下：

class Solution { 
    public:
        int threeSumClosest(vector<int>& nums, int target) { 
            sort(nums.begin(),nums.end());
            int len = nums.size();
            int ans = 100000;
            for(int p1 = 0;p1 < len-2;p1++)
            { 
                if((p1>0) && (nums[p1] == nums[p1-1])) continue;
                int p2 = p1 + 1;
                int p3 = len - 1;
                while((p1<p2)&&(p2<p3))
                { 
                    int newsum = nums[p1] + nums[p2] + nums[p3];
                    if(abs(newsum-target) < abs(ans-target))
                        ans = newsum;
                    if(newsum == target)
                    {    
                        return target;
                    }
                    else if(newsum > target)
                        p3--;
                    else
                        p2++;
                }                   
            }
            return ans;
        }
    };

结果：  
![在这里插入图片描述][20200305100426414.png]

[leetcode 16_python]: https://blog.csdn.net/nanashi_F/article/details/100169350
[16. _ - _LeetCode]: https://leetcode-cn.com/problems/3sum-closest
[20200304222048201.png]: https://img-blog.csdnimg.cn/20200304222048201.png
[leetcode 15.]: https://blog.csdn.net/nanashi_F/article/details/100166194
[20200305100426414.png]: https://img-blog.csdnimg.cn/20200305100426414.png