Fork me on GitHub

Two Sum

题目介绍

LeetCode 1. Two Sum,题目的意思简单来说就是给 Target,从数组中找到两个数和,同一个数不可以用两次,且我在测试的时候发现会有同一个值出现两次的情况。

解题方法

暴力求解

很简单的方式,两个 for loop 就能解决,时间复杂度为 O(n²)。

1
2
3
4
5
6
7
8
9
10
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == target - nums[i]) {
return new int[] { i, j };
}
}
}
throw new IllegalArgumentException("No two sum solution");
}

散列表

散列表,Table Hash。这边只是很简单的应用,后续会介绍更加复杂的应用。简单的思想就是将数组中的数不断的读入,key - 是数组中的值,value - 是遍历数组的 index。写入的时候先判断 Target - nums[i] 的 key 是否存在 value。如果存在说明这个数已经被写入了,那么就找到了这两个数;如果不存在则写入数组。算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var dictionary = [Int: Int]()
for i in 0..<nums.count {
if let item = dictionary[target - nums[i]] {
return [item, i]
}
dictionary[nums[i]] = i
}
return []
}
}

PS: 本来没打算写这篇博客,主要是我朋友在写这一条的写了 Python 算法,如下:

1
2
3
4
5
6
7
8
9
10
import copy
def two_sum(nums, target):
for index, item in enumerate(nums):
a = target - item
list = copy.copy(nums)
del list[index]
if a in list:
if nums.index(a) == index:
return [index,list.index(a)+1]
return [index, nums.index(a)]

简单的来看,是读取一个数首先删除本身,然后去判断 target - item 是不是存在数组中。我开始很疑惑,在没有使用散列表的情况下,只用数组解出来一定是牺牲了时空复杂度。果然问题在 if a in list:,python 的语法糖在做这句话的时候,其实是做了 For loop,所以时间复杂度为 O(n²)。迷惑了我朋友很久才想通的问题,大家在刷题的时候一定要注意:高级语言的语法糖和数据结构在带来遍历的同时,在处理方式上面可能会存在你不知道的时空耗费。


版权声明



Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证

本文首发于Ivan’s Blog | 叶帆的博客博客( http://yeziahehe.com ),版权所有,侵权必究。

本文链接:http://yeziahehe.com/2017/10/09/TwoSum/