Python算法练习之解决两数之和问题

本次算法题来自力扣官网，感兴趣的同学可以去力扣官网学习！

语言版本：Python 3.10

编译器版本：Pycharm 2021.3.2

题目：两数之和

给定一个整数数组nums和一个整数目标值target，
请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。
但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

示例1

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 

示例2

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例3

输入：nums = [3,3], target = 6
输出：[0,1]

第一时间的做题思路

首先，我也是昨天才开始决定有空看看算法题锻炼一下自己的思维能力，现在我算法能力超级的弱，还请大家谅解谅解哈哈哈👻

怎么说呢，我昨天看见这道题的时候，我的第一想法也是暴力解法，直接使用两层for循环枚举数组中的每一个数x，寻找数组中是否存在（target-x），然后我就去问了我几个朋友，他们看见这个题的第一反应也是通过枚举法，之后我去看了一下官方的解题思路，第一个方法也是暴力枚举，但是这个方法的时间复杂度过高，做算法练习的目的也在于如何优化和找到更好的解题方法，在这里我就不对第一种解法做说明了，我相信大家应该都能看懂，我就在下面附上官方的代码：

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 []

回顾哈希表相关知识

官方给的第二种解题思路就是哈希表，在这里我也着重的说一下利用哈希表解题，哈希表的相关知识我还是上学期学C语言的数据结构学的，现在也差不多忘记很多了，所以我上网翻阅了很多资料，先来回顾一下有关哈希表的相关知识，这样也方便后续的解题。

哈希表是什么

哈希表（Hash tavle)又称散列表，通过哈希函数（Hash Function）来计算对应键值，再根据关键码值(Key value)将所需查询的数据影射到表中的一个位置而实现数据访问的一种数据结构。

哈希表是字典的实现原理，字典通过哈希表来存储数据，而读取的时候也是通过哈希表来获取对应的值。Python中的字典（dict）类型就是哈希表的原理，存储方式就是[key：value]，通过键来快速访问value，字典再访问操作上的时间复杂度是O(1)

处理冲突

常见的解决冲突的方法有三种：

1.开放定址法

H_i = (H(key) + d_i) % d_i) % m (i = 1, 2, …, n)

其中H(key)是哈希函数，m为表长，d_i为增量序列

方法名称	取值方式
线性探测再散列	di=1，2，3，…，m-1
二次探测再散列	di=12，-12，22，-22，…，k2，-k2 (k<=m/2)
伪随机探测再散列	di=伪随机数序列

2.再哈希法

H_i=RH_i(key) (i = 1, 2, …, k)

同时构造多个不同的哈希函数，在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生

3.链地址法

将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中。

在这里我就简单的回顾一下有关哈希表的知识，不再深究，如果想更加深入的了解哈希表的底层逻辑的话，可以自己上网进行查阅学习，作者能力有限，更深层的我暂时还理解不了

回到题目

题目要求我们自己给定一个整数数组，然后再给一个整数目标值，让我们遍历该数组找到两个整数和刚好等于目标值，然后返回对应两个整数的下标，这种遍历会从左到右依次遍历，我们需要的是找到最先两个符合要求的整数，然后停止遍历并返回它们的下标。

我们可以利用哈希字典查找，通过Python中的enumerate()方法将数值对应关系放入哈希字典中，然后依次用目标值target减去数组中的每一个值，并判断该值是否在哈希表中，如果不在就依次填入哈希表中，直到检测出目标值target减去数组中的某个值X产生的值在哈希表出现冲突，先将值X放入哈希表然后返回该值和与其产生冲突的值的下标，返回类型是列表。

举个例子：

传入数组：[1, 2, 3, 6]

target = 5

① 5 -1 = 4 4不在哈希表中，填入1

value(值)	1
key(下标)	0

② 5 - 2 = 3 3不在哈希表中，填入2

value(值)	1	2
key(下标)	0	1

③ 5 - 3 = 2 2在哈希表中，产生冲突，填入与其冲突的值后面

value(值)	1	2	3
key(下标)	0	1	2

到这里已经完成了题目的要求，已经找到了哈希表中两个值和为目标值的两个整数，现在进行代码实现

代码实现：

class Solution:
    def incoming_parameters(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hash_table = dict()
        for i, num in enumerate(nums):
            if (target - num) in hash_table:
                return [hash_table[target - num], i]
            hash_table[nums[i]] = i
        return hash_table


if __name__ == '__main__':
    a = Solution()
    print(a.incoming_parameters([1, 2, 3, 6], 5))
    print(a.incoming_parameters([2, 7, 11, 15], 9))
    print(a.incoming_parameters([3, 2, 4], 6))
    print(a.incoming_parameters([3, 3], 6))

它运行的结果是：

[1, 2]
[0, 1]
[1, 2]
[0, 1]

可以看出，结果和我们举例还有和官方给的示例一样，所以程序已经正常实现。

补充知识：

代码中我们使用的枚举方法是Python中的enumerate()方法，它的使用语法是：

enumerate(iterable, start = 0)

它的两个参数是：

• iterable：支持迭代的序列、迭代器或者对象
• start(可选)：从这个数字开始计数，如果省略，则默认从0开始计数

enumerate()方法返回的对象也是一个枚举对象

接下来我们来测试一下两种方法的运行时间，进行对比一下。

对比运行速度

1.暴力枚举法

from horology import timed

class Solution:
    @timed
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: 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 []


if __name__ == '__main__':
    a = Solution()
    print(a.twoSum([1, 2, 3, 6], 5))

它的运行结果是：

twoSum: 2.6 us
[1, 2]

2.哈希表法

from horology import timed

class Solution:
    @timed
    def incoming_parameters(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hash_table = dict()
        for i, num in enumerate(nums):
            if (target - num) in hash_table:
                return [hash_table[target - num], i]
            hash_table[nums[i]] = i
        return hash_table


if __name__ == '__main__':
    a = Solution()
    print(a.incoming_parameters([1, 2, 3, 6], 5))

它的运行结果是：

incoming_parameters: 2.1 us
[1, 2]

暴力枚举法的时间复杂度是O(n²)，而哈希表法的时间复杂度是O(1)，然后通过程序运行时间对比，也会发现哈希表法比暴力枚举法快了很多。

我上面所用的测试程序运行时间的方法可能有些人没有用过，在这里我用的一个第三方的插件模块，叫horology ，你可以在终端通过pip install horology的方法下载这个模块，使用方法也很简单。

from horology import Timing

with Timing(name='Important calculations: '):
    prepare()
    do_your_stuff()
    finish_sth()

它将输出：

Important calculations: 12.43ms

它还有一个更简单写法：

from horology import timed

@timed
def main():
    ...

它将输出：

main: 2.1 us

==注意：==这个方法适用于Python 3.6或者更高版本！

我在这里使用的就是最简单的写法，很方便。

复杂度分析

最后附上我在网上找的一个显示各种方法的时间复杂度的图片

输出：

Important calculations: 12.43ms

它还有一个更简单写法：

from horology import timed

@timed
def main():
    ...

它将输出：

main: 2.1 us

==注意：==这个方法适用于Python 3.6或者更高版本！

我在这里使用的就是最简单的写法，很方便。

复杂度分析

最后附上我在网上找的一个显示各种方法的时间复杂度的图片