Leetcode：1.Two Sum

这是崔斯特的第八十九篇原创文章

1. Two Sum

难度: Easy

刷题内容

原题连接： https://leetcode.com/problems/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, 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].

解题方案

思路 1

- 时间复杂度: O(N^2)- 空间复杂度: O(1) *

暴力解法，两轮遍历

beats 12.80%

class Solution(object):
    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]

Runtime: 5248 ms, faster than 12.80% of Python3 online submissions forTwo Sum.
Memory Usage: 13.5 MB, less than 51.76% of Python3 online submissions for Two Sum.

太吓人，遍历太慢了。

思路 2

A + B = target，同样的：A = target - B，我们可以维护一个字典来记录说访问过的值。

这里我犯了个错，我先贴代码

class Solution:
    def twoSum(self, nums: List[int], target: int)-> List[int]:
        lookup = {}
        for i, j in enumerate(nums):
            if target - j not in lookup.values():
                lookup[i] = j
            else:
                return [i, nums.index(target - i)]

Runtime: 568 ms, faster than 34.25% of Python3 online submissions forTwo Sum.
Memory Usage: 14.1 MB, less than 9.73% of Python3 online submissions for Two Sum.

虽然比第一种解法好，但是才超过34.25%，这也太慢了吧。

其实是我写法不够好，字典维序反了，这样查找会慢很多，每次查找都需要查询 lookup.values() ，这其实是一个列表，应该就是这里导致速度变慢。

改良后的代码：

class Solution:
    def twoSum(self, nums: List[int], target: int)-> List[int]:
        lookup = {}
        for i, j in enumerate(nums):
            if target - j in lookup:
                return [i, nums.index(target - j)]
            else:
                lookup[j] = i

Runtime: 40 ms, faster than 73.58% of Python3 online submissions for Two Sum.
Memory Usage: 14.1 MB, less than 10.10% of Python3 online submissions for Two Sum.

比73.58%的要快，果然细节决定成败啊。