1.LeetCode刷题笔记-Tow Sum

description

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)
如下：

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if(nums[i]+nums[j] == target):
                    return [i,j]

运行时间在倒数12.5%

第二种解法，Hash表，查找元素和映射之间关系最佳的方式就是用Hash，Python中直接采用内置dict
代码如下：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = {}
        for i in range(len(nums)):
            x = nums[i]
            if target-x in dict:
                return ([dict[target-x], i])
            dict[x] = i  

特别注意的坑是，不要先将所有元素放入dict中，因为dict必须每个键对应一个项，如果对应了多个，则后面的会顶替前面的元素。

超过89%的提交