Solution 1 (Runtime: 1288 ms Memory Usage: 14.6 MB)
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in nums:
j = target - i
indice_1 = nums.index(i)
indice_2 = indice_1 + 1
tmp_nums = nums[indice_2: ] # you may not use the same element twice
if j in tmp_nums:
return(indice_1, tmp_nums.index(j)+indice_2) # not use nums.index(j) because 'you may not use the same element twice'
Solution 2 (Runtime: 60 ms Memory Usage: 15.2 MB)
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
numspool = {} #dictionary
for i in range(len(nums)):
if target - nums[i] not in numspool:
numspool[nums[i]] = i
else:
return(numspool[target - nums[i]], i)
Time complexity of solution 1 is O(n*n). Time complexity of solution 2 is O(n). Because dictionary offer O(1) lookup time. Space complexities of both of them are O(n).
步步发财 