问题网址：https://leetcode.com/problems/two-sum/description/
问题描述： 给定一个整数数组，返回两个整数的下标，使它们的和等于一个给定的值。 可以假设每个输入都只有一个解决方案，也就是说不会两次使用相同的元素。
问题样例：
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].一个简单想法： brute force的做法很简单。 循环遍历每个元素x，并找到是否有另一个值等于target-x。
#include<vector> #include<stdexcept> vector<int> twoSum1(vector<int>& nums, int target) { for (int i = 0; i < nums.size(); i++) { for (int j = i + 1; j < nums.size(); j++) { if (nums[i] + nums[j] == target) { return {i, j}; } } } throw logic_error("No Solution."); }时间复杂度：O（n^2）
改进想法： 为了提高我们的时间复杂度，我们需要一种更有效的方法来检查数组中是否存在补码。 如果补码存在，我们需要查找其索引。 将数组中的每个元素映射到其索引的最佳方法是哈希表。 我们通过哈希表将查找时间从O（n）减少到O（1）。哈希表是为了这个目的而建立的，它支持在几乎恒定的时间内快速查找。 我说“接近”，是因为如果发生冲突，查找可以退化为O（n）时间。 但是查询哈希表应该被分摊O（1）时间，只需要仔细选择哈希函数。 一个简单的实现使用两次迭代。 在第一次迭代中，我们将每个元素的值和其下表添加到哈希表中。 然后，在第二次迭代中，我们检查表中是否存在每个元素的补码（target-nums[i]）。 当然这个补码不能是nums[i]本身。 在c++11中，使用unordered_map作为哈希表的数据结构。
vector<int> twoSum2(vector<int>& nums, int target) { unordered_map<int, int> map; for (int i = 0; i < nums.size(); i++) { map[nums[i]] = i; } for (int i = 0; i < nums.size(); i++) { int complement = target - nums[i]; if (map.find(complement) != map.end() && map[complement] != i) { return {i, map[complement]}; } } throw logic_error("No Solution."); }时间复杂度：O（n）
再次改进想法： 事实证明，我们可以一次性完成。 当我们迭代并将元素插入到表中时，我们也回顾一下检查当前元素的补码是否已经存在于表中。 如果存在，我们已经得到一个解并立即返回。
vector<int> twoSum3(vector<int>& nums, int target) { unordered_map<int, int> map; for (int i = 0; i < nums.size(); i++) { int complement = target - nums[i]; if (map.find(complement) != map.end()) { return {map[complement], i}; } map[nums[i]] = i; } throw logic_error("No Solution."); }时间复杂度：O（n）
