两数之和问题
题目描述：在给定的数组nums中找到两个数之和等于目标值target。
1. 暴力方法
检索数组中所有的两数组合，直到找到和等于target的组合。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
l = len(nums)
for i in range(l):
for j in range(i+1, l):
if nums[i] + nums[j] == target:
return [i, j]
return [-1, -1]
复杂度分析：
由于要检索所有可能的两数组合，因而时间复杂度为 。空间复杂度为
。
2. 两遍哈希表
题目要求寻找, 换个思路，对于每个i，只需要检索数组中是否存在j，使
， 这里要注意
。那么自然就会想到检索元素值与其索引的最快方法：哈希表。哈希表通过空间换时间的方式将检索的时间复杂度从
降到
。
我们可以通过两次遍历，第一次将每个元素的值以及它的索引添加到哈希表中，然后在第二次遍历中，根据所需要的值查找到它的索引，当然这里同样需要注意，找到的值不能是第一个数本身。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for index, val in enumerate(nums):
hashmap[val] = index
for i, num in enumerate(nums):
j = hashmap.get(target-num)
if j is not None and i != j:
return [i, j]
return [-1, -1]
复杂度分析：
由于使用了哈希表，只需要两次遍历就可以找到两数的组合。因此时间复杂度为 。而哈希表带来了空间开销，空间复杂度为
。
注意：
由于使用python中的字典来实现哈希表，python中的字典当加入的元素key值一样时，并不会有冲突处理的机制，而是直接覆盖，这一点和实际的哈希是有区别的。因此如果判例中数组含有相同值的数字时，该段程序可能就不能得到正确结果。例如 ，该段代码会认为没有可选的组合。如果要改进则需要自己手动实现一个哈希表的数据结构，进行冲突处理。
3. 一遍哈希表
继续分析上面使用了哈希表后的算法，其实在第一遍向哈希表中插入新元素时，可以先查找当前的表中是否有所需要的元素，如果查找到了就直接输出结果，如果没有则将新元素插入，继续后面的检索。通过这种方式，我们可以通过一次遍历就找出答案。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for index, val in enumerate(nums):
j = hashmap.get(target-val)
if j is None:
hashmap[val] = index
else:
return [j, index]
return [-1, -1]
复杂度分析：
通过在向哈希表中插入新元素之前先检索，只需要一次遍历就可以找到答案。因此时间复杂度为， 空间复杂度仍然为
。
三数之和问题
题目描述： 在给定的数组nums中找到三个数的组合，三个数之和为给定值0。
1. 暴力法
这个问题是两数之和问题的进阶版，同样可以使用暴力检索方法，通过穷举所有组合来找到答案。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
l = len(nums)
res = []
for i in range(l)[0:l-2]:
for j in range(i+1, l)[0:l-1]:
for k in range(j+1, l):
if nums[i]+nums[j]+nums[k] == 0:
res.append([nums[i], nums[j], nums[k]])
return res
复杂度分析：
通过使用三次遍历找到目标组合，时间复杂度为 ，空间复杂度为
。
注意：
该段代码并未考虑结果中存在重复组合的问题。题目中要求结果中不能包含重复组合，因此是不符合要求的。
2. 使用哈希表
类比两数之和问题，同样可以使用哈希表对暴力方法进行优化。在寻找第三个数时使用哈希表进行检索。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
l = len(nums)
res = []
hashmap = {}
for i in range(l)[0:l-2]:
for j in range(l)[i+1:l-1]:
k = hashmap.get(-nums[i]-nums[j])
if k is None:
hashmap[-nums[i]-nums[j]] = j
else:
res.append([nums[i], nums[j], -nums[i]-nums[j]])
return res
复杂度分析：
通过使用哈希表只需要两次遍历就可以找出可行组合，将时间复杂度降为 ,空间复杂度为
。
注意：
同样的，使用哈希表仍没有解决答案中存在重复组合的问题。
