给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
第一次:
根据题目的提示写了一段代码
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
lst = []
for i in range(0,len(nums)-1):
if nums[i] + nums[i+1] == target:
lst.append(i)
lst.append(i+1)
return lst
提交代码显示解读错误\color{red}{解读错误}解读错误
发现问题是一层for循环不够,改写代码
第二次:
for循环再套一次循环
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
lst = []
l = len(nums)
for i in range(0,l):
for j in range(i+1,l):
if nums[i] + nums[j] == target:
lst.append(i)
lst.append(j)
return lst
这次显示超出时间限制\color{red}{超出时间限制}超出时间限制
这就是没有考虑算法,而且显然两层for循环太浪费时间,这时候就考虑怎样能减少代码运行时间。
第三次:
对上面程序进行再次改写,运用python特有的字典\color{red}{字典}字典
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dic = dict()
l = len(nums)
for i in range(0, l):
temp = target - nums[i]
if temp in dic:
return [dic[temp], i]
map_a[nums[i]] = i
这次再运行代码,运行成功。
第四次:
python中还有个函数是enumerate
套for循环使用enumerate函数
>>>seq = ['one', 'two', 'three']
>>> for i, element in enumerate(seq):
... print i, element
...
0 one
1 two
2 three
这题解法还可以是:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dic = dict()
for i, ele in enumerate(nums):
if target - ele in dic:
return [dic[target - ele], i]
dic[ele] = i
提交代码
不过没想到enumerate()函数运行速度居然没提升…
这题运用的是哈希表\color{blue}{哈希表}哈希表
哈希表简单来说就是能把值和地址对应起来,就像python里的字典有value和key,一个value对应一个key值,或者是像上面enumerate()函数用for循环时i和ele。
提醒一下
上面代码都是可以直接在Leecode里实现
如果是pycharm或其他软件实现需要改代码,给个例子:
def twoSum(nums, target):
dic = dict()
for i, ele in enumerate(nums):
if target - ele in dic:
return [dic[target - ele], i]
dic[ele] = i
nums = [3, 2, 4]
target = 6
out = twoSum(nums, target)
print(out)
第一天结束
over