两数之和 56，608暴力查找排序加双指针
两数之和 56，608暴力查找排序加双指针
和蔼的zhxing
发布于 2018-09-04 13:09:07
发布于 2018-09-04 13:09:07
看到了就一块做了，两个题的要求差不多，条件不同： 给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。 你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 1 到 n，不是以 0 开头。 样例 给出 numbers = [2, 7, 11, 15], target = 9, 返回 [1, 2].
两个数的条件不同，56给出的数组是乱序的，608给的数组是顺序的。
暴力查找
对于每一个数，在数组中查找和其和为目标数的数，注意两个数的索引不能相同，这样的时间复杂度是O(n^2)，谁都能想到，不推荐。
排序加双指针
608
这个思路就比较好了，对于608给出的数据，直接排序加双指针就ok了,记得最后给索引加1。
vector<int> twoSum(vector<int> &nums, int target) {
auto beg=nums.begin();
auto end=nums.end()-1;
vector<int> res;
int s=0;
//两头
while(beg<end)
{
if(*beg+*end==target) //等于的话就刚刚好
{res.push_back(beg-nums.begin()+1);
res.push_back(end-nums.begin()+1);
return res;
}
if(*beg+*end<target) //小于的话就增加第一个
{
beg++;
}
else //大于的话就减小后一个
{
end--;
}
}
// write your code here
}56
这个倒是可以排序，但是记得要同时把索引也保存起来，因为最后要求返回的是索引，可以把值和索引做成一个pair放入vector里面，然后根据值来排序，这里的排序规则要自己写，sort函数的第三个参数是支持的，然后再双指针就可以了。
static bool MyComp(pair<int, int> a, pair<int, int> b)
{
return a.first < b.first;
}
vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> res;
vector<pair<int, int>> nums;
for (size_t i = 0; i<numbers.size(); i++)
{
nums.push_back(make_pair(numbers[i], i)); //把key和value分别存入map
}
sort(nums.begin(), nums.end(),MyComp); //自定义排序规则
auto beg = nums.begin();
auto end = nums.end() - 1;
while (beg != nums.end())
{
if(beg->first+end->first==target)
{
res.push_back(beg->second + 1);
res.push_back(end->second + 1);
break;
}
else if (beg->first + end->first < target)
beg++;
else if (beg->first + end->first > target)
end--;
}
sort(res.begin(),res.end());
return res;
// write your code here
}既然用pair来做可以，那么干脆用map来做就行了，因为map是按照key进行自动排序的，不用自己排序，要注意需要用multimap来做，不要去重，用insert添加进去。 但是map就不能用双指针了，map的迭代器不支持减操作，但是map自己的find函数还是可以用的，按照key查找，返回对应的迭代器，如果不存在则返回尾后。 这样说起来vector也是可以用find的，但是为了体会这个过程，还是不用了的好。程序如下：注意map查找时，可能返回当前遍历的元素，要排除掉。
vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> res;
multimap<int,int> nums;
for (size_t i = 0; i<numbers.size(); i++)
{
nums.insert(make_pair(numbers[i],i)); //把key和value分别存入map
}
auto beg = nums.begin();
while (beg != nums.end())
{
auto f = nums.find(target-beg->first);
if (f != nums.end()&&f!=beg) //不能等于自己，要不两个索引是一样的了。
{
res.push_back(beg->second + 1);
res.push_back(f->second + 1);
break;
}
beg++;
}
sort(res.begin(), res.end());
return res;
// write your code here
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.12.04 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录