首页 > 其他 > 详细

Leetcode-两数之和

时间:2018-04-25 10:01:30      阅读:508      评论:0      收藏:0      [点我收藏+]

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

 自己的思路如下:将容器nums中的元素,依次用target减去,放入另一个容器b中,位置对应,既然同样的元素不能被重复利用,那么依次对比b中的元素有没有在nums中的其他位置出现,如果出现了,我们就找到了两个的位置。另外就是要求返回的是一个数对,我们需要额外建立个容器c,将找到的位置放入容器c中返回。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        vector<int>b,c;
        for(int i=0;i<nums.size();i++)
        {
             b.push_back(target-nums[i]);
        }
        for(int i=0;i<b.size();i++)
            for(int j=0;j<nums.size();j++)
            {
                if(b[i]==nums[j])
                {
                    if(i!=j)
                    {
                        c.push_back(i);
                        c.push_back(j);
                        return c;
                    }
                }
            }
    }
};

那么有没有更好的算法呢,当然是有的,上述算法的时间复杂度达到了o(n^2),经过参考,特记录优秀算法如下

vector<int> twoSum(vector<int>& nums, int target)
{
  unordered_map<int, int> m;
  vector<int> c;
  for (int i = 0; i < nums.size(); ++i)
  {
    if (m.count(target - nums[i]))
    {
      c.push_back(m[target-nums[i]]);
      c.push_back(i);
      return c;
    }
    m[nums[i]] = i;
  }
}

其中的count函数是algorithm头文件中包含的,count(first,end,pre),参数中first代表查询的起始位置,是一个迭代器,end代表查询的终止位置,也是一个迭代器,pre是要查询的元素,返回的是元素出现的次数。count函数和find函数类似,但find函数返回的是该元素的迭代器。

上述程序中count返回的值是1或者0,因为在unorder_map中,元素只允许出现一次,相同的元素会被覆盖。如果查询到了target-nums[i],则返回i和找到的位置,比如{2,7,4,11},target=6.map中会得到(2,0)(7,1)(4,2),可以发现target-4=2,已经在map中找到了,返回找到那个的位置(肯定在前面,所以先返回),再返回本位置。

Leetcode-两数之和

原文:https://www.cnblogs.com/mini-coconut/p/8940046.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!