leetcode 1. 两数之和题目：
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
第一种解决方法（暴力解决）:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i, v in enumerate(nums):
for l, k in enumerate(nums):
if i == l:
continue
if k + v == target:
return [i,l]
复杂度分析：
时间复杂度：O(n^2)O(n 2 )， 对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)O(n) 的时间。因此时间复杂度为 O(n^2)O(n 2 )。
空间复杂度：O(1)O(1)。
第二种方法（hash值）：
利用list的index() 和collections中defaultdict
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
from collections import defaultdict
d = defaultdict(list)
[d[v].append(i) for i, v in enumerate(nums)]
for i, v in enumerate(nums):
second_value = target - v
try:
index_li = d[second_value]
for l in index_li:
if i == l:
continue
return [i, l]
except KeyError:
continue
复杂度分析：
时间复杂度：O(n)O(n)， 我们只遍历了包含有 nn 个元素的列表一次。在表中进行的每次查找只花费 O(1)O(1) 的时间。
空间复杂度：O(n)O(n)， 所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 nn 个元素。
原文网址：http://www.chenxm.cc/post/710.html
