两数之和python编程
时间: 2023-11-12 09:08:19 浏览: 47
两数之和是一道经典的算法题,给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。这个问题可以用多种方法来解决,其中最常见的方法是暴力法和哈希表法。
暴力法的时间复杂度是 O(n^2),空间复杂度是 O(1)。它的思路是枚举数组中的每一对数,判断它们的和是否等于目标值。如果找到了一对数,就返回它们的下标。如果没有找到,就返回一个空列表。
哈希表法的时间复杂度是 O(n),空间复杂度也是 O(n)。它的思路是先将数组中的每个数和它的下标存储到一个哈希表中,然后遍历数组,对于每个数,在哈希表中查找是否存在另一个数与它的和等于目标值。如果找到了这样的数,就返回它们的下标。如果没有找到,就返回一个空列表。
下面是两数之和的Python代码示例:
暴力法:
def two_sum1(nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
哈希表法:
def two_sum2(nums, target):
hash_table = {}
for i, num in enumerate(nums):
if target - num in hash_table:
return [hash_table[target - num], i]
hash_table[num] = i
return []
除了这两种方法,还有一种时间复杂度为 O(nlogn) 的排序 + 双指针法,它的思路是先对数组进行排序,然后定义两个指针,分别指向数组的首尾,循环直到找到答案或者指针相遇。具体实现可以参考引用中的代码示例。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)