Two Sum
2019-02-20 本文已影响0人
羊yang678
https://leetcode.com/problems/two-sum/
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
思路：暴力破解的时间复杂度为O(n2).考虑使用map来保存数组数值和下标的关系，在遍历map key时，查找target-key是否存在。
class test:
def two_sum(self,nums,target):
nums_map = {}
for i ,num in enumerate(nums):
nums_map[num] = i
other_num = target-num
if other_num in nums_map:
return nums_map[other_num],nums_map[target-other_num]
return -1,-1
if __name__ == "__main__":
nums=[2,3,1,4,7]
test = test()
print test.two_sum(nums,9)
