Leetcode（1）-两数之和

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

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

示例:

给定 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（1）-两数之和

最新文章

热门文章