目录
题目背景
这个题目用常规的双循环就可以完成。
但不是最优解。为什么?
看看他的步骤数:
N =【3,2,4】
求结果为6的两个元素坐标如下,
1). 3+2 = 5 不等于
2). 3+4 = 7 不等于
3). 2+4 = 6 等于,获取坐标【1,2】
规律:
2个数 = 1 个步骤
3个数 = 3 个步骤
4个数 = 6 个步骤
5个数 = 10 个步骤
6个数 = 15 个步骤
7个数 = 21 个步骤
......
如果有N个元素, 则需要N个步骤,那么记作 O(N)。下面分析那么这个算法的大O是:
约等于 N(N) = $ N^2 $
这个算法的时间复杂度为:O($ N^2 $).
有什么办法能降低这个时间复杂度吗?
解题思路
def twoSum(nums, target):
# 创建一个哈希表来存储值和索引
num_to_index = {}
# 遍历数组
for i, num in enumerate(nums):
# 计算当前数字的补数
complement = target - num
# 检查补数是否在哈希表中
if complement in num_to_index:
# 如果在,返回补数的索引和当前索引
return [num_to_index[complement], i]
# 如果不在,将当前数字及其索引存入哈希表
num_to_index[num] = i
# 如果没有找到符合条件的两个数,返回空列表或抛出异常
return []
print(twoSum([3, 2, 4], 6))
模拟运行过程:
# {} 创建map
# 1) 6 - 3 = 3 , 判断 3不在map,继续
# map加上{3:1}
# 2) 6 - 2 = 4 , 判断 4不在map,继续
# map加上{3:1,2:2}
# 3) 6 - 4 = 2 , 判断 2在map ,返回当前4和2的坐标,结束。
# map{3:1,2:2}
标签:map,Hash,index,步骤,个数,实践,num,补数,两数
From: https://www.cnblogs.com/mysticbinary/p/18389836