算法（2）- 两数之和
2021-06-06 21:05
标签：元素 出现 def rate 分析 数组下标 rgb 给定一个整数数组 顺序 示例 1： 示例 2： 示例 3： 提示： 双循环，没啥好讲的 算法（2）- 两数之和 标签：元素 出现 def rate 分析 数组下标 rgb 给定一个整数数组 顺序 原文地址：https://www.cnblogs.com/poloyy/p/14594900.html题目
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
输入：nums = [3,2,4], target = 6
输出：[1,2]
输入：nums = [3,3], target = 6
输出：[0,1]
2
只会存在一个有效答案
正确答案一：穷举法
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 []
复杂度分析
正确答案二：哈希表
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 []
思路分析
复杂度分析