【一天一道Leetcode】两数之和

看那个码农

共 2143字,需浏览 5分钟

 ·

2021-02-21 05:41


本篇推文共计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。


【快速写好毕业论文】你不得不知晓的七个常用文献搜索平台


【秋招纪实录】一篇特别正经的【腾讯】求职经验分享


【秋招纪实录】一篇特别正经的【建信金科】求职经验分享


【秋招纪实录】一篇特别正经的【无领导小组讨论】经验分享


【秋招纪实录】一篇特别正经的【国企】求职经验分享



☆ END ☆

你与世界

只差一个

公众号

浏览 37
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报