LeetCode OJ #1 Two Sum

恩，据说刷LeetCode比较好玩，于是乎从第一题开始吧。
题目：
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
思路：
这道题给的Hint是二叉树，我有点不太懂，用二叉树实现了一个版本，不过会超时。想了下还是用map的黑科技吧，反正没限制内存大小。（再黑科技一点可以直接用数组，就是数据多的话要找到最小/最大值做好映射）
代码：

class Solution {
private:
	map<int, int> valTable;
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		for (int i = 0; i < nums.size(); i++) {
			int val = nums[i];
			valTable[val] = i + 1;
		}
		for (int i = 0; i < nums.size(); i++) {
			int ne = target - nums[i];
			map<int, int>::iterator result = valTable.find(ne);
			if (result != valTable.end()) {
				int nextIndex = result->second;
				int currIndex = i + 1;
				if (currIndex == nextIndex)
					continue;
				vector<int> retIndices;
				if (currIndex > nextIndex) {
					retIndices.push_back(nextIndex);
					retIndices.push_back(currIndex);
				}
				else {
					retIndices.push_back(currIndex);
					retIndices.push_back(nextIndex);
				}
				return retIndices;
			}
		}
	}
};

运行结果：
我只超过了30.19%的队友，哈哈~

 
 
2018 refined (beats 92.29%):

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, size_t> num_indices; // <number, indices>
        for (size_t i = 0; i < nums.size(); ++i)
        {
            auto num = nums[i];
            if (num_indices.count(target - num) > 0)
            {
                return {num_indices[target - num], i};
            }
            num_indices[num] = i;
        }
        return {-1, -1};
    }
};