两数之和
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]解答¶
这边题目一开始的思路是，直接判断相差元素在后面的数组中是否存在，所以写出了如下代码:
In [1]:
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i in range(len(nums)):
element = nums[i]
right = nums[i+1:]
if target-element in right:
index = nums[i+1:].index(target-element)
return [i, i+index+1]
return []
但是实际上，这里有一个 index 操作是非常消耗性能的。
后来想了想，发现可以换个思路，从左值数组中找，并且更换数据结构，使用字典存放下标来加快查找效率。
于是写下新的代码:
In [2]:
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
left = {}
for i in range(len(nums)):
element = nums[i]
if target - element in left:
return [left[target-element], i]
left[element] = i
return []
解答完毕 :)
Comments !