*LeetCode應(yīng)該是更新了測(cè)試數(shù)據(jù)，時(shí)隔近兩年一樣的O(n^2)代碼提交，慢了十幾倍
給一列未排序的數(shù)列，問(wèn)是否存在不同位置的兩個(gè)數(shù)，相加之和為target
方法一：用dict存每個(gè)數(shù)字出現(xiàn)的位置，然后掃過(guò)數(shù)列中每個(gè)數(shù)nums[i]，看target-nums[i]是否也在數(shù)列中，注意數(shù)列可能有重復(fù)數(shù)，此時(shí)要記錄所有出現(xiàn)過(guò)的下標(biāo)，因?yàn)轭}目保證唯一解，所以如果是答案是兩個(gè)一樣的數(shù)nums[j]，那dict[nums[j]]長(zhǎng)度只能是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]]
方法二：暴力兩重循環(huán)
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]
方法三：先排序，再用兩個(gè)指針從最左和最右向中間掃描，類(lèi)似第167題