返回信息流leetcode第一题求正解。
我用循环遍历求和， 提交时报超时了，输入是一个很大的数组。
跪求正解，学习用。。
这是一条镜像帖。来源：北邮人论坛 / cpp / #87752同步于 2015/7/3
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
[问题]菜鸟求助
headforpower
2015/7/3镜像同步3 回复
订阅后，新回复会通过你的通知中心匿名送达。
3 条回复
【 在 headforpower 的大作中提到: 】
: leetcode第一题求正解。
: 我用循环遍历求和， 提交时报超时了，输入是一个很大的数组。
: 跪求正解，学习用。。
题目是 two sum
【 在 headforpower 的大作中提到: 】
: 题目是 two sum
我的答案：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret;
int index1=1;
int index2=0;
vector<int>::const_iterator it1 = nums.begin();
vector<int>::const_iterator it2;
for(; it1!=nums.end(); ++it1)
{
index2 = index1+1;
for(it2 =it1+1; it2!=nums.end();++it2)
{
if((*it1 + *it2)== target)
{
break;
}
}
if (it2!=nums.end())
{
break;
}
index1++;
}
ret.push_back(index1);
ret.push_back(index2);
return ret;
}
};
【 在 headforpower 的大作中提到: 】
: leetcode第一题求正解。
: 我用循环遍历求和， 提交时报超时了，输入是一个很大的数组。
: 跪求正解，学习用。。
好吧，在网上搜到答案了。
vector<int> twoSum(vector<int>& numbers, int target)
{
vector<int> vecRes;
multimap<int, int> map_index;
for (int i = 0; i < numbers.size(); i++)
{
map_index.insert(make_pair(numbers[i], i));
}
for (int j = 0 ; j < numbers.size() - 1; j++)
{
int nTemp = target - numbers[j];
multimap<int, int>::iterator it = map_index.find(nTemp);
for (int k = 0; k != map_index.count(nTemp); k++)
{
if ( it->second > j)
{
vecRes.push_back(j + 1);
vecRes.push_back(it->second + 1);
return vecRes;
}
it++;
}
}
return vecRes;
}