1. Two Sum

题目：

解答：

题意即在一个数字集合中，取出两个数，其数字之和等于target。

• 方法一： 使用遍历寻值，时间上界为O(n²)，耗时较长
• 方法二： 将数列排序后，在已排序的数列上，使用一次O(n)方法查找出来，时间上界为O(nlogn + n)，主要是排序时间
• 方法三： 使用哈希表存储每个数值的位置，为了保证查找到重复key数据，使用unordered_multimap数据结构，注意equal_range的方法返回的两个值，first是开始迭代器，second是末尾迭代器，且不包含second。
• 方法四： 使用unordered_map来处理。注意是怎样避免对相同key的处理的。

代码：

class Solution {
public:
    // 方法一：遍历寻值
    vector<int> twoSumV1(vector<int> &numbers, int target) {
        vector<int> vec;
        for( vector<int>::iterator i = numbers.begin();i != numbers.end() - 1;++i ) 
            for( vector<int>::iterator j = i + 1;j != numbers.end();++j )
                if( *i + *j == target ) {
                    vec.push_back(*i);
                    vec.push_back(*j);
                }
        return vec;
    }
    // 方法二，先排序后查找
    vector<int> twoSumV2(vector<int> &numbers, int target) {
        vector<int> vec;
        if( numbers.size() < 2 )    return vec;
        vec = numbers;
        sort( vec.begin(),vec.end() );
        int i = 0,j = vec.size() - 1;
        while( i != j ) {
            if( vec[i] + vec[j] > target )  j--;
            else if( vec[i] + vec[j] < target ) i++;
            else    break;
        }
        vector<int> dest;
        for( int t = 0;t < numbers.size();++t ) {
            if( numbers[t] == vec[i] )  {
                dest.push_back(t+1);
                continue;
            }
            if( numbers[t] == vec[j] )  dest.push_back(t+1);
        }
        return dest;
    }
    // 方法三，使用unordered_multimap
    typedef unordered_multimap<int, int> nummultimap;
    vector<int> twoSumV3(vector<int>& nums, int target) {
        vector<int> result;
        unordered_multimap<int, int> nummap;
        int len = nums.size();
        for(int i = 0;i < len; ++i){
            nummap.insert({nums[i], i});
        }
        for(int i = 0;i < len; ++i){
            int remainvalue = target - nums[i];
            if(remainvalue * 2 != target){
                if(nummap.find(remainvalue) != nummap.end()){
                    result.push_back(nummap.find(remainvalue)->second);
                    result.push_back(nummap.find(target-remainvalue)->second);
                    return result;
                }
            }
            else{
                auto range = nummap.equal_range(remainvalue);
                auto p = range.first;
                if(++p != range.second){
                    for(unordered_multimap<int,int>::iterator it = range.first;it != range.second; ++it){
                        result.push_back(it->second);
                    }
                    return result;
                }
            }
        }
        return result;
    }
    // 使用unordered_map方式处理
    vector<int> twoSumV4(vector<int>& nums, int target) {
        unordered_map<int,int> nummap;
        vector<int> result;
        int len = nums.size(), remainvalue;
        for(int i = 0;i < len; ++i){
            nummap[nums[i]] = i;
        }
        for(int i = 0;i < len; ++i){
            int remainvalue = target - nums[i];
            if(nummap.find(remainvalue) != nummap.end() && nummap[remainvalue] != i){
                result.push_back(nummap[remainvalue]);
                result.push_back(i);
                return result;
            }
        }
        return result;
    }
};