leetcode_two_sum

leetcode上easy的一道题。

用cpp跑了两种算法。

1.先将拷贝一份vector。对新的数组排序，并找出相加等于target的对应值first、second。再在原始数组中扫一遍，找出first和second的相应位置。代码如下。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> nums_copy = nums;
        vector<int> rst;
        sort(nums_copy.begin(), nums_copy.end());
        auto it = nums_copy.begin();
        auto last_it = it + nums_copy.size()-1;
        int first,second;
        while(it != last_it)
        {
            int sum = *it + *last_it;
            if(sum < target)
            {
                it++;
            }
            else if(sum > target)
            {
                last_it--;
            }
            else
            {
                first = *it;
                second = *last_it;
                break;
            }
        }
        it = nums.begin();
        for(;it != nums.end(); it++)
        {
            if(*it == first)
                rst.push_back(it-nums.begin());
            else if(*it == second)
                rst.push_back(it-nums.begin());
        }
        return rst;
    }
};

结果：9ms，超过96.22%。

2.使用map，存储<数值，数值的位置>。遍历整个数组。遍历过程中，其中map中key存储target－已遍历元素的值，value存储已遍历元素的位置。如果下一个元素在map中可以找到相应的key，则满足条件；如果下一个元素找不到相应的key，就将存入map中。代码如下。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> m;
        vector<int> rst;
        auto it = nums.begin();
        size_t i = 0;
        for(;it != nums.end(); it++,i++)
        {
            auto find_it = m.find(*it);
            if(find_it == m.end())
            {
                m.insert(pair<int,int>(target-*it,i));
            }
            else
            {
                rst.push_back(find_it->second);
                rst.push_back(i);
            }
        }
        return rst;
    }
};

结果：19ms，超过58.82%。这里使用了unordered_map，要比使用map快(29ms)。unordered_map是基于hash实现的，map是基于tree实现的。