首页 / 更多教程 / Leetcode#16 3Sum Closest

Leetcode#16 3Sum Closest

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Leetcode#16 3Sum Closest，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1266字，纯文字阅读大概需要2分钟。

内容图文

原题地址

 

跟2Sum、3Sum、4Sum类似，都是：排序+搜索+剪枝

令sum = num[i] + num[j] + num[k] + (-target)（将-target看做一个必选的数），那这道题就跟4Sum（参见这篇文章）几乎一样了，变成了寻找最接近0的和。

需要剪枝的地方：

1. 数字太小，肯定不是最优解

2. 数字太大，肯定不是最优解

3. 数字重复

其他优化：

寻找最后一个数字可以用二分查找

 

代码：

             1
            int
             res;

             2
             3
            void dfs(vector<int> &num, int ans, int pos, int left) {
 4if (left == 0) {
 5if (abs(ans) < abs(res))
 6       res = ans;
 7return;
 8  }
 910// 二分查找最后一个数11if (left == 1) {
12int l = pos;
13int r = num.size() - 1;
14while (l <= r) {
15int m = (l + r) / 2;
16       res = abs(ans + num[m]) < abs(res) ? ans + num[m] : res;
17if (ans + num[m] < 0)
18         l = m + 1;
19else20         r = m - 1;
21    }
22return;
23  }
2425   unordered_set<int> old;
26for (int i = pos; i < num.size(); i++) {
27// 数字重复28if (old.find(num[i]) != old.end())
29continue;
30// 数字太大31if (num[i] * left + ans > abs(res))
32break;
33// 数字太小34if (num[num.size() - 1] * (left - 1) + num[i] + ans < -abs(res))
35continue;
36    old.insert(num[i]);
37     dfs(num, ans + num[i], i + 1, left - 1);
38  }
39}
4041int threeSumClosest(vector<int> &num, int target) {
42  sort(num.begin(), num.end());
43   res = num[0] + num[1] + num[2] - target;
44   dfs(num, -target, 0, 3);
45return res + target;
46 }

 

原文：http://www.cnblogs.com/boring09/p/4263125.html

内容总结

以上是互联网集市为您收集整理的Leetcode#16 3Sum Closest全部内容，希望文章能够帮你解决Leetcode#16 3Sum Closest所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1203339.html

来源：【匿名】