题目要求
从数组中找出两个数,这两个数加在一起等于目标值target,返回这两个数的下标
暴力法
思路
指针 i 不动,指针 j 向后扫描数组,直到找到 nums[i] + nums[j] 的值等于 target 或者 j 大于数组长度为止 如果没找到,指针 i 加 1,重复上述过程,直到找到或者指针 i 大于数组长度为止
代码
class Solution(object
):
def
twoSum(self
, nums
, target
):
length
= len(nums
)
for i
in range(0,length
- 1):
for j
in range(i
+ 1,length
):
if nums
[i
] + nums
[j
] == target
:
return[i
,j
]
return[]
运行结果
哈希法
思路
把数组中的数映射到散列表中,映射方法:数组的索引是散列表的值,数组的值是散列表的索引,即hashset [ nums [ i ] ] = i 一边映射一边查找散列表中索引为 target - nums[ i ] 的项是否为空,不为空就找到了结果 如果先映射后遍历会导致使用重复数值
代码
class Solution(object
):
def
twoSum(self
, nums
, target
):
hashset
= {}
for i
in range(len(nums
)):
if hashset
.get(target
- nums
[i
]) is not None
:
return[i
,hashset
.get(target
-nums
[i
])]
hashset
[nums
[i
]] = i
return []
运行结果