Two Sum问题：给定一个数组nums和一个正整数target，试从数组中找出2个元素，它们相加之和恰好为target。
难度：容易
思路：用Hash表建立反向索引（很多查找类问题都可以用索引来优化性能）
陷阱：index1 != index2
代码：
class Solution:
# @param {integer[]} nums
# @param {integer} target
# @return {integer[]}
def twoSum(self, nums, target):
nums_dict = {}
for idx, num in enumerate(nums):
nums_dict[num] = idx
for index1, num in enumerate(nums):
index2 = nums_dict.get(target - num)
if index2 is not None and index2 != index1:
return [index1 + 1, index2 + 1]
return [0, 0]
时间复杂度：O(n)
空间复杂度：O(n)
网友评论