题目描述：

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.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.

题目大意：

给定一个整数数组，从中找出两个数的下标，使得它们的和等于一个特定的数字。

可以假设题目有唯一解。

测试用例如题目描述。

解题思路：

利用字典idxDict保存数字num到其下标idx的映射。

遍历查找数字num与目标数target的“互补数”时只需查找idxDict[target - num]是否存在即可。

时间复杂度：O（n），因为dict的存取开销为O(1)

Python代码：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        idxDict = dict()
        for idx, num in enumerate(nums):
            if target - num in idxDict:
                return [idxDict[target - num], idx]
            idxDict[num] = idx

 

本文链接：http://bookshadow.com/weblog/2015/02/03/leetcode-two-sum/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码