leetcode两数之和—python
2018-07-16 本文已影响0人
mieecho
一、暴力穷举
for i,num in enumerate(nums):
for j,num2 in enumerate(nums[i+1:]):
if num == target - num2:
return(i,j)
第一次提交最后一个数据超时,时间复杂度O(n^2)【正常应该不会超时才对】
二、字典优化
dic = {}
l = len(nums)
for i in range(l):
if target - nums[i] in dic:
return(dic[target-nums[i]],i)
else:
dic[nums[i]] = i
把第i个数和它的位置存在字典中,看list中后续的数与之相加是否等于target
记录一个错误的想法——index返回的是num第一次出现的位置,则数据如3+3=6就会出错
#dic = {}
#for numin nums:
#if target - numin dic:
#print(dic[target-num],nums.index(num))
#break
# else:
#dic[num] = nums.index(num)