算法（2）- 两数之和
题目
- 给定一个整数数组 nums 和一个整数目标值 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]提示：
2 <= nums.length <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案正确答案一：穷举法
双循环，没啥好讲的
def twoSum(nums: List[int], target: int) -> List[int]:
lens = (len(nums))
for i in range(lens - 1):
for j in range(i + 1, lens):
if nums[i] + nums[j] == target:
return [i, j]
return []复杂度分析
- 时间复杂度：O(N^2)，其中 N 是数组中的元素数量；最坏情况下数组中任意两个数都要被匹配一次
- 空间复杂度：O(1)
正确答案二：哈希表
def twoSum2(nums: List[int], target: int) -> List[int]:
# 创建一个哈希表。在 Python 里面用字典代替
res = {}
# 使用 enumerate 函数，第一个返回值是下标，第二个返回值是列表元素值
for i, num in enumerate(nums):
# 先查询是否存在 target- num 的值
if (target - num) in res.keys():
# 存在则直接返回
return [res[(target - num)],i]
# 不存在则将当前的元素加到字典中
res[num] = i
return []思路分析
- 注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高
- 因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素
- 如果存在，我们需要找出它的索引
- 使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)降低到 O(1)
复杂度分析
- 时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x
- 空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销
- 用空间换时间
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-03-30 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录