[LeetCode]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.

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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

暂无评论

张贴您的评论