NC61.两数之和

class Solution {
public:
    /**
     * 
     * @param numbers int整型vector 
     * @param target int整型 
     * @return int整型vector
     */
    vector<int> twoSum(vector<int>& numbers, int target) {
        // write code here
        std::vector<int> ans;
        std::unordered_map<int, int> map;
        std::unordered_map<int, int>::iterator itor;
        int sz = numbers.size();
        for (int i = 0; i < sz; ++i) {
            itor = map.find(numbers[i]);
            if (itor != map.end()) {
                ans.emplace_back(itor->second + 1);
                ans.emplace_back(i + 1);
                break;
            }
            map.insert(std::pair<int, int>(target - numbers[i], i));
        }
        
        return ans;
    }
};

解题思路：

难点1：能否想到用Hash表来做映射，能想到这道题基本就能做出来；

难点2：Hash表里存什么很重要。完全将数组丢进Hash表，将Hash表当做数组的一个快速检索索引也能做；更优的办法是，边遍历数组，边将差丢入Hash表，这样Hash表就是个结果集，更加快速；

知识点：

知识点1：unordered_map与map的区别，前者是Hash表，时间复杂度近似常数，后者实现原理是红黑树，时间复杂度是lgN；

知识点2：map迭代器的声明：

std::unordered_map<int, int>::iterator itor; 

知识点3：map中寻找某个key是否存在，使用以下方法

itor = map.find(number);
if (itor != map.end()) {
	//...
}

知识点4：map的KV插入，使用以下方法最为高效

map.insert(std::pair<int, int>(i, j));

知识点5：map通过迭代器取值

int i = itor->first;
int j = itor->second;