题目
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例给定 nums = [2, 7, 11, 15]，target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回[0, 1]
思考
最简单、最直接的想法就是暴力的嵌套的双循环，遍历每个元素计算。空间复杂度虽然是O(1)，但是时间复杂度却是O($n^2$)，因为对于每个元素，都试图遍历它以外的所有元素来求解，这一次循环就耗费O(n)时间。所以对于长度越长的数组来说效率越低。
所以需要一种更有效的方法来检查数组中是否存在所需的元素。如果存在，就返回它的索引。这里可以使用哈希表。通过牺牲空间换取时间。可以将查找时间从O(n)降底到O(1)，哈希表正是为此目的而构建，它支持以近似恒定的时间进行快速查找。之所以“近似”，是因为一旦出现冲突，查找时间可能退化到O(n)。只要仔细的挑选哈希函数，在哈希表中进行查找的用时应当被摊销为O(1)。
使用哈希表的话，时间复杂度为O(n)，因为查找时间缩短到了O(1)。空间复杂度为O(n)。
解题思路
关键点在于 nums[i] + nums[j] = target，即等于 nums[i] = target - nums[j]。可以做个哈希表，表里面存储以target - nums[j](目标元素)为键，当前索引为值。在迭代并将元素插入到表中的同时，进行检查表中是否已经存在当前元素所对应的目标元素。如果存在，即找到对应解，立即返回。
Python实现
Python里面的字典就是利用哈希表存储的，可以拿来直接使用。
class Solution: def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ if len(nums) <= 1: return [0, 0] d = dict() for i in range(len(nums)): if nums[i] in d: return [d[nums[i]], i] else: d[target - nums[i]] = i在LeetCode上跑了44ms
C++实现
C++的话，需要使用里面的hash_map，std里面还有map，map底层是使用红黑树存储的。查找时间复杂度是O($logn$)。
有关hash_map的介绍可以阅览《详细解说STL hash_map系列》。那么正常情况下什么时候用map，什么时候用hash_map？需要具体看应用，复杂度为常数级别O(1)的hash_map就一定比O($logn$)级别的map要好，hash_map的hash函数以及解决地址冲突等都需要耗时，而且hash表是以空间效率来换取时间效率的，所以hash_map所耗内存更大。一般情况下，数据量很大的时候，可以考虑使用hash_map，可以提高查找效率。但如果需要谨慎使用内存的时候，就应该考虑使用map了。
(2018/07/09追加，根据C++ 11标准的推荐，用unordered_map代替hash_map。关于unordered_map可以参考下面文章的介绍)
class Solution{ public: std::vector<int> twoSum(std::vector<int>& nums, int target) { std::unordered_map<int, int> dict; std::vector<int> result; for(int i = 0; i < nums.size(); ++i) { auto it = dict.find(nums[i]); if(it != dict.end()) { result.push_back(dict[nums[i]]); result.push_back(i); return result; } else { dict.insert(std::pair<int, int>(target - nums[i], i)); } } return result; }};在LeetCode上跑了8ms