两数之和（two-sum）
这是LeetCode上一道十分经典的题目，存在多种解法，难度是简单，但后面难度更高的三数之和、四数之和，其实也是由这道题演变而来的。
题目
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
解题
方法一： 暴力法
暴力法很逻辑很简单，采用两轮错位嵌循环，计算两个位置的数字之和是否等于目标值，因为题目中说明了只有两个整数的和是等于target，所以一旦找到直接 return 就行，十分简单粗暴。
class Solution(object):
def twoSum(self, nums, target):
for i in range(len(nums) - 1):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return i, j
这种写法很好理解，得益于Python语言的简洁，上面核心部分的代码甚至可以简化为一行：
chain.from_iterable([[i, j] for i in range(len(nums) - 1) for j in range(i + 1, len(nums)) if nums[i] + nums[j] == target])
因为是嵌套循环，所以时间复杂度是O()，空间复杂度是O(1)，提交了也没毛病，在所有 python 提交中击败了31.08%的用户，这种方法在运行效率上不是很高。面试时如果没有太好的思路，可以尝试用暴力法来解决。如果能在短时间内写出上面的代码，至少说明你对语言本身还是很熟练的，代码的功底也还可以。
方法二：哈希大法
正确的思路是采取空间换时间的办法，使用一个哈希表缓存。思路如下：
题目要求我们找出两个和为target的数，也就是
nums[i] + nums[j] = target。转换一下，也就是
target - nums[i] = nums[j]。把nums[i]和i以键值对的形式存到哈希表中，注意存的是{值:下标}这种格式 。
由此可以看出，我们下次再遍历nums的时候，如果哈希表中存在一个数是target与当前数的差，那么那个数就是我们要找的数。而哈希表中查询的时间复杂度是O(1)，所以整体函数的效率提高了一个数量级。
-
再一次循环nums，这次一边循环一边检索第4步存储的哈希表，如果能检索到，说明符合条件，立即返回，over。这里面有一个小坑，如果有一个数n，target与n的差恰好也等于n，这样就会在哈希表中查询到n自己，显示是不符合题目要求的，所以在判断的时候要注意过滤掉。
代码如下：
class Solution(object): def twoSum(self, nums, target): d = {n: i for i, n in enumerate(nums)} for i, n in enumerate(nums): # 在哈希表中查询的时候，注意过滤掉当前数自身 if target - n in d and d[target - n] != i: return i, d[target - n]方法二一共遍历了两次nums，时间复杂度为O(2N)，同时引入一个新的字典，空间复杂度变成了O(N)，所以说是用空间换时间。
方法三：优化的哈希大法
方法二的其实还可以再优化一下，只用遍历一次nums就可以得到结果。在遍历的同时把数据写入哈希表中，并进行查询，这样最坏的情况下时间复杂度也就是O(N)。
class Solution(object):
def twoSum(self, nums, target):
d = {}
for i in range(len(nums)):
if target - nums[i] in d:
return i, d[target - nums[i]]
d[nums[i]] = i
因为在字典中查询的时候，当前数字还没有放到哈希表中，所以省去了一个判断条件，代码逻辑变的更加简单。
