leetcode 入门第一题 4ms? 8ms? Two Sum

时间:2021-11-25 05:14:40

今天开启leetcode

入门第一题

题意很简单,就是一个数组中求取两数之和等于目标数的一对儿下标

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 = ; 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[]{i.second,j->second};
return vector<int>(a,a+);

额外加时了4ms。。还是算了=.=

(二)从当前位置之前二分剩余

接着看了下这道题的提交情况,发现竟然有4ms过的,(当然也有0ms的,非正常人,这个可以忽略)

官方代码:

leetcode 入门第一题 4ms? 8ms?  Two Sum

结果跑了8ms,可能是我脸黑,也可能数据增加了,或者,是个玄学测评机?

可以看到这个代码就属于从头到尾一次插入,刚开始是空的,边找边插,找完之后再把当前位置插入序列,这样就可以避免找到自己本身

咦~,这貌似是个好办法,学习了~

到此,还不能说明方法(一)不好或者方法(一)略微复杂

我们对于找答案佛系一点,或许就,见到了奇迹

leetcode 入门第一题 4ms? 8ms?  Two Sum

【3,3】target = 6,同样,第一次(3,0)会找到(3,0),我们可以跳过,(3,1)自然会找到(3,0)进行匹配,自动化随缘法

另:leetcode可能不支持unordered_map或者unordered_multimap中的lower_bound和upper_bound,我也不清楚到底有没有,我只知道VS是有的。

这篇单单是记录一下leetcode初体验,给出的样例题目当然非常简单了,欢迎大伙儿入坑~

感谢您的阅读,生活愉快~