#leetcode刷题之路16-最接近的三数之和
2019-03-12 08:23:02来源:博客园 阅读 ()
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
这个题和之前的的三数之和有非常相近之处:
思路:依然是先排序,然后依次遍历。这里加上点约束来优化,首先是我们要知道,在递增的数组中,越往后遍历三数之和越大,如果(三数之和-target)的值大于当前的差值(正数),那么立刻停止循环。如果等于target则直接返回target。
#include <iostream> #include <vector> #include <algorithm> using namespace std; int threeSumClosest(vector<int>& nums, int target) { int len = nums.size(); int dif = INT_MAX; int ans = target; sort(nums.begin(), nums.end()); for (int i = 0; i<len - 2; i++) { for (int j = i + 1; j<len - 1; j++) { for (int k = j + 1; k<len; k++) { //cout << nums[i] << " " << nums[j] << " " << nums[k]; int tdif = (nums[i] + nums[j] + nums[k]) - target; if (tdif == 0) return target; if (abs(tdif)<dif) { dif = abs(tdif); ans = nums[i] + nums[j] + nums[k]; } //cout << " " <<ans<<endl; if (tdif> dif) break; } } } return ans; } int main() { vector<int> a = { 1, 2, 4, 8, 16, 32, 64, 128}; int target=82; int ans=threeSumClosest(a,target); std::cout << ans << std::endl; return 0; }
原文链接:https://www.cnblogs.com/biat/p/10516709.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- OI之路 2019-10-25
- 小白的C++之路——求质数 2019-10-25
- #leetcode刷题之路19-删除链表的倒数第N个节点 2019-03-13
- #leetcode刷题之路17-电话号码的字母组合 2019-03-13
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash