*LeetCode应该是更新了测试数据，时隔近两年一样的O(n^2)代码提交，慢了十几倍
给一列未排序的数列，问是否存在不同位置的两个数，相加之和为target
方法一：用dict存每个数字出现的位置，然后扫过数列中每个数nums[i]，看target-nums[i]是否也在数列中，注意数列可能有重复数，此时要记录所有出现过的下标，因为题目保证唯一解，所以如果是答案是两个一样的数nums[j]，那dict[nums[j]]长度只能是2
1 #1
2 #Runtime: 54 ms
3 #Memory Usage: 15.5 MB
4
5 class Solution(object):
6 def twoSum(self, nums, target):
7 """
8 :type nums: List[int]
9 :type target: int
10 :rtype: List[int]
11 """
12 dict = {}
13 for i in range(len(nums)):
14 if nums[i] in dict:
15 dict[nums[i]].append(i)
16 else:
17 dict[nums[i]] = [i]
18 for i in range(len(nums)):
19 if target - nums[i] == nums[i]:
20 if len(dict[nums[i]]) > 1:
21 return dict[nums[i]]
22 else:
23 if target - nums[i] in dict:
24 return [dict[nums[i]][0], dict[target - nums[i]][0]]
方法二：暴力两重循环
1 #1
2 #Runtime: 7316 ms
3 #Memory Usage: 14.4 MB
4
5 class Solution(object):
6 def twoSum(self, nums, target):
7 """
8 :type nums: List[int]
9 :type target: int
10 :rtype: List[int]
11 """
12 l = len(nums)
13 for i in range(0, l, 1):
14 for j in range(i + 1, l, 1):
15 if nums[i] + nums[j] == target:
16 return [i, j]
方法三：先排序，再用两个指针从最左和最右向中间扫描，类似第167题