[LeetCode] 1. Two Sum

链接：Two Sum

描述：在数组中找到两个数，他们相加的和等于目标，返回这两个数的索引。

思路：可以采用朴素解法，两层循环，但如果数据过多，将会导致超时。更好的办法是采用哈希表保存对应加数的索引并搜索。

解法：

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> res;
        map<int,int> pos;
        int sz = (int)numbers.size();

        for(int i=0; i<sz; i++) {
            // 搜索与当前加数对应的另一加数
            auto it = pos.find(target - numbers[i]);
            // 如果没找到，则把当前加数的索引保存起来，并继续搜索
            if(it == pos.end()) {
                pos[numbers[i]] = i;
            }
            // 找到了另一个加数
            else{
                res.push_back(it->second);
                res.push_back(i);
                break;
            }
        }
        return res;
    }
};