LeetCode 1 in Python. Two Sum (两数之和)

两数之和算法思想很简单，即找到nums[i]和nums[j]==target-(nums[i])返回[I, j ]即可。问题在于，简单的两层遍历循环时间复杂度为O()，而通过构建一个hash表就可将时间复杂度降至O(n)。本文给出两种方法的代码实现。

示例：

图1 两数之和输入输出示例图 

方法一：枚举(时间复杂度为为O())

代码 ：

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

方法二：哈希表（时间复杂度为O(n)）

代码：

class Solution:
    def twoSum(self, nums, target):
        hashmap = {}
        for i, num in enumerate(nums):
            if target - nums[i] in hashmap:
                return [i, hashmap[target - nums[i]]]
            hashmap[num] = i
        return []