【一天一道Leetcode】两数之和

题目描述

题目描述：

给定一个整数数组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)。