Leetcode 第一题 《两数之和》

原题目

定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

Leetcode给出了三种解法

• 暴力法 复杂度O(n^2)
• 两遍Hash表法，创建Hash表一次O(n)，遍历查找O(n)
• 一遍Hash

一遍Hash算法说明

1. 第一个元素添加到hash表，key是num，value是index。
2. 计算target - 第二个元素，
   • 如果在Hash表中，遍历结束。命中index（1）和当前元素index（2），返回[1,2]
   • 如果Hash查找没有命中，将2添加到Hash表
3. 遍历nums数组。

Python 实现

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dict = {}
        dict[nums[0]] = 0
        for i in xrange(1,len(nums)):
            x = nums[i]
            if target-x in dict:
                return (dict[target-x], i)
            dict[nums[i]] = i

评分，战胜99.96%的python提交记录