题意很简单, 就是一个数组中求取两数之和等于目标数的一对儿下标
1. 暴力 n^2
两个 for 循环遍历
用时 0.1s 开外
代码就不用写了
2. 二分 nlogn
我们可以遍历选择每一个元素 , 然后二分剩余(target - ai)
(一)从全序列二分剩余
这就需要考虑下标和自己重叠的情况, 比如[3,3] ,target:6
于是我们就需要判重叠
代码就长成下面这样了(8ms)
- class Solution {
- public:
- vector<int> twoSum(vector<int>& nums, int target) {
- multimap<int, int> P;
- for (int i = 0; i <nums.size(); ++i)
- P.insert(pair<int, int>(nums[i], i));
- for (auto i : P)
- {
- map<int, int>::iterator j = P.find(target - i.first);
- if (j != P.end() && i.first + j->first == target)
- {
- if (i.second == j->second)
- {
- ++j;
- if (i.first + j->first != target)continue;
- }
- vector<int> V;
- V.push_back(i.second);
- V.push_back(j->second);
- return V;
- }
- }
- }
- };
因为后面四行用于 return 的代码太长了, 看着不舒服, 于是改成了
- int a[2]{
- i.second,j->second
- };
- return vector<int>(a,a+2);
额外加时了 4ms.. 还是算了 =.=
(二)从当前位置之前二分剩余
接着看了下这道题的提交情况, 发现竟然有 4ms 过的,(当然也有 0ms 的, 非正常人, 这个可以忽略)
官方代码:
结果跑了 8ms, 可能是我脸黑, 也可能数据增加了, 或者, 是个玄学测评机?
可以看到这个代码就属于从头到尾一次插入, 刚开始是空的, 边找边插, 找完之后再把当前位置插入序列, 这样就可以避免找到自己本身
咦~, 这貌似是个好办法, 学习了~
到此, 还不能说明方法 (一) 不好或者方法 (一) 略微复杂
我们对于找答案佛系一点, 或许就, 见到了奇迹
[3,3] target = 6, 同样, 第一次 (3,0) 会找到 (3,0), 我们可以跳过,(3,1) 自然会找到 (3,0) 进行匹配, 自动化随缘法
另: leetcode 可能不支持 unordered_map 或者 unordered_multimap 中的 lower_bound 和 upper_bound, 我也不清楚到底有没有, 我只知道 VS 是有的.
这篇单单是记录一下 leetcode 初体验, 给出的样例题目当然非常简单了, 欢迎大伙儿入坑~
来源: http://www.bubuko.com/infodetail-2850402.html