1. Two Sum
Problem
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2,7,11,15],
target =9,
Because nums[0] + nums[1] =2+7=9,
return[0,1].
给定一个整数数组，当两个数相加等于目标值时，返回其下表。
你可以假设每一组输入都仅有一个确切的结果，你不可以使用同样的元素两次。
Solution
Brute Force/暴力破解
遍历每一个元素x，并且寻找另一个元素y，使得y = target - x。
复杂度分析
时间复杂度：O(n2)
对于每个元素，我们试图通过遍历数组中的其他元素O(n2)来找到匹配的结果。因此，时间复杂度是O(n2)。
空间复杂度：O(1)
Tow-pass Hash Table/二次遍历散列表
为了改进时间复杂度，我们需要一种更有效的方式来检查数组中是否存在对应的元素。如果对应元素存在，我们需要查询它的下标。我们可以通过Hash表来存储每一个元素的下标。
我们使用hash表来将查询的时间复杂度从O(n)降到O(1)。hash表的查询时间近似于一个常量，但是当碰撞发生时，一次查询可能需要O(n)的时间。当hash方法选择得当时，一次查询的时间仅需要O(1)。
一个简单的实现就是使用二次遍历。在第一次遍历时，我们将每一个元素的值和下标添加到hash表中。然后，在第二次遍历时，我们查询每个元素的对应值是否存在(target - nums[i])。注意对应值不能是nums[i]自身。
复杂度分析
时间复杂度：O(n)。我们遍历了包含n个元素的列表两次。通过hash表将查询时间下降到O(1)，因此时间复杂度是O(n)。
空间复杂度：O(n)。存储n个元素的hash表使用了额外的存储空间，因此空间复杂度是O(n)。
One-pass Hash Table/一次遍历散列表
我们可以使用一次遍历来实现。当我们遍历并且插入元素的时候，我们同时回看并且复查是否有对应的元素已经存在于散列表中。如果存在我们就得到了一个解，并且立刻返回结果。
复杂度分析
时间复杂度：O(n)。我们遍历了包含n个元素的列表一次。每次查询耗时O(1)。
空间复杂度：O(n)。存储n个元素的hash表使用了额外的存储空间。
