【一天一道Leetcode】两数之和
本篇推文共计2000个字,阅读时间约3分钟。
01
题目描述
题目描述:
给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值的那两个整数,并返回它们的数组下标。
示例:
输入:nums = [2,4,12,13], target = 16
输出:[1,2]
解释:因为 nums[1] + nums[2] == 16 ,返回 [1, 2]
02
代码分析
既然需要在数组中匹配出和为目标值的那两个整数,则可以从数组第一个数开始,用枚举法利用数组遍历的方式找出和为目标值的那两个数字。
由此可以得到
代码一
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n=len(nums)
for i in range(n):
for j in range(i+1,n):
if nums[i] + nums[j] == target:
return [i,j]
return []
但是这种方法从复杂度上分析
时间复杂度:O(N^2),N是数组中的元素数量
空间复杂度:O(1)
因此如果想进一步进行复杂度优化的话,
可以引用哈希表
哈希(hash)表的定义:
哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。
也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
说起来可能感觉有点复杂,
最典型的的例子就是字典,如果我想要获取“安”字详细信息,我肯定会去根据拼音"an"去查找拼音索引(或者也可以是偏旁索引),我们首先去查"an"在字典的位置,查了一下得到“安”,安在字典的第4页。我们就翻到字典第4页找到安。
这过程就是键码映射,
同时这个过程也可以用公式f(key)表示。
安就是关键字(key),f()就是字典索引,也就是哈希函数,查到的页码4就是哈希值。
由此可以得到
代码二
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashtable = dict() 字典
for i, num in enumerate(nums):
if target - num in hashtable:
return [hashtable[target - num], i]
hashtable[nums[i]] = i
return []
这个方法叫做查找表法,在遍历数组的同时,记录一些信息,以省去一层循环结构。
原理如下:
假设nums=[1,3,4,7,6],与之
对应的下标为[0,1,2,3,4]
设定target=9
从数组第一个数字开始,nums的第一个数字1之前没有数字,所以先将nums的第一个数字1存入哈希表中
hashtable={1}
接下来循环到了nums的第二个数字3,
target-3=6
6目前没在哈希表中,所以继续将3存入哈希表
hashtable={1,3}
接下来循环到了nums的第三个数字4,
target-4=5
5目前没在哈希表hashtable={1,3}中,所以继续将4存入哈希表
hashtable={1,3,4}
接下来循环到了nums的第四个数字7,
target-7=2
2目前没在哈希表hashtable={1,3,4}中,所以继续将7存入哈希表
hashtable={1,3,4,7}
接下来循环到了nums的第五个数字6,
target-6=3
3目前在哈希表hashtable={1,3,4,7}中,所以此时nums的3,6就是我们要找的两个数。
此时输出3,6的下标[0,3]即可
其中的enumerate用法如下:
seq = ['one', 'two', 'three']
for i, element in enumerate(seq):
print(i, element)
输出:
0 one
1 two
2 three
代码二
时间复杂度:O(N),其中 N 是数组中的元素数量。
空间复杂度:O(N)。
【年终总结】你好2021,再见2020。
【快速写好毕业论文】你不得不知晓的七个常用文献搜索平台
【秋招纪实录】一篇特别正经的【腾讯】求职经验分享
【秋招纪实录】一篇特别正经的【建信金科】求职经验分享
【秋招纪实录】一篇特别正经的【无领导小组讨论】经验分享
【秋招纪实录】一篇特别正经的【国企】求职经验分享
你与世界
只差一个
公众号