Two Sum

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)