Fork me on GitHub

Leetcode：1.Two Sum

发表于 | 分类于 
这是崔斯特的第八十九篇原创文章

1. Two Sum

难度: Easy

刷题内容

原题连接：https://leetcode.com/problems/two-sum

内容描述：

1
2
3
4
5
6
7
8
9
10
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].

解题方案

Python

思路 1

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

暴力解法，两轮遍历

beats 12.80%

1
2
3
4
5
6
7
8
9
10
11
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，我们可以维护一个字典来记录说访问过的值。

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

1
2
3
4
5
6
7
8
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()，这其实是一个列表，应该就是这里导致速度变慢。

改良后的代码：

1
2
3
4
5
6
7
8
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%的要快，果然细节决定成败啊。

Golang

这些天正好在学习Golang的基础语法，做这题应该是没什么问题，思路什么的和上面的一样。代码如下：

two_sum.go

1
2
3
4
5
6
7
8
9
10
11
12
13
package two_sum
func twoSum(nums []int, target int) []int {
	index := make(map[int]int, len(nums))
	for i, b := range nums {
		if j, ok := index[target-b]; ok {
			return []int{j, i}
		}
		index[b] = i
	}
	return nil
}

two_sum_test.go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package two_sum
import (
	"github.com/stretchr/testify/assert"
	"testing"
)
type para struct {
	one []int
	two int
}
type ans struct {
	one []int
}
type question struct {
	p para
	a ans
}
func Test_OK(t *testing.T)  {
	ast := assert.New(t)
	qs := []question{
		{
			p: para{
				one: []int{3, 2, 4},
				two: 6,
			},
			a: ans{
				one: []int{1, 2},
			},
		},
		{
			p: para{
				one: []int{3, 2, 4},
				two: 8,
			},
			a: ans{
				one: nil,
			},
		},
	}
	for _, q := range qs {
		a, p := q.a, q.p
		ast.Equal(a.one, twoSum(p.one, p.two), "输入: %v", p)
	}
}

作为还没写过单元测试的人来说，刚开始接触这种真的很不适应，慢慢来吧。

Runtime: 4 ms, faster than 100.00% of Go online submissions for Two Sum.

Memory Usage: 3.4 MB, less than 63.51% of Go online submissions forTwo Sum.

Go和Python的对比，简直了

这个解法额外的创建了一个map来储存状态，所以在空间上不够好，看到别人的解法，如下：

1
2
3
4
5
6
7
8
9
10
11
func twoSum(nums []int, target int) []int {
	length := len(nums)
	for i := 0; i < length; i++ {
		for j := i + 1; j < length; j++ {
			if nums[i]+nums[j] == target {
				return []int{i, j}
			}
		}
	}
	return nil
}

这就相当于上面开始的暴力解法，牺牲时间来换取空间，最后的结果是：

Runtime: 36 ms, faster than 41.39% of Go online submissions for Two Sum.

Memory Usage: 2.9 MB, less than 68.92% of Go online submissions for Two Sum.

时间是原来的9倍，变化真的大！