EverydayTopics-2023-Oct-30

题目

1. 两数之和

解法

暴力

第一想到的就是暴力：一个个算呗，但是这样感觉效率还是太低了，总之贴上代码：

1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n=len(nums)
        for i in range(n-1):
            n1=nums[i]
            for j in range(i+1,n):
                n2=nums[j]
                if n1+n2==target:
                    return [i,j]

其他解法

注意到这里的目的是对于x，查找target-x是否在该表中。那么用搜索的想法的话，可以用2分法，时间复杂度为O(nlogn)。

官方解法里给出了一个O(n)的算法：创建一个哈希表，遍历所有的数据，对于每一个x，查找target-x是否在这之中，如果不存在的话则将x存入表中，因为x与target-x肯定是双向的，所以同样也可以用target-x来查找x。利用哈希表的查找效率为O(1)，一次遍历即可。

贴上代码：

1
2
3
4
5
6
7
8
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 []

补充知识

enumerate函数

这其中

1
enumerate(nums)

是python中的枚举函数，用法如下：

enumerate() 是一个 Python 内置函数，用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。

1
2
3
4
5
6
7
8
citys = ["jinan", "qingdao", "yantai", "zibo"]
for index,city in enumerate(citys):
    print(index,city)
# 输出： 
0 jinan
1 qingdao
2 yantai
3 zibo

enumerate() 还接受第二个参数（可选），该参数允许决定索引从哪个数字开始。如果可选的 start 参数不存在，则默认情况下索引从 0 开始。

1
2
3
4
5
6
7
8
citys = ["jinan", "qingdao", "yantai", "zibo"]
for index,city in enumerate(citys,101):
    print(index,city)
# 输出：
101 jinan
102 qingdao
103 yantai
104 zibo

哈希表

哈希表（hash tab），亦为散列表。是一个将查找表中的关键字映射成为关键字对应函数的地址。当然这一题中我们并不关注哈希表是如何实现的，但实际上哈希表的哈希函数（散列函数）也是这个内容考察的重要一部分。此处不再赘述