Two Sum

题目:

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

思路:

在数组中找出和为目标数字的元素坐标,最直观的思路就是两次遍历,查找和为target的元素,但时间复杂度为O(n2),并不是一个很好的算法。
另一种算法,是依次取出数组中的元素,然后用target减去该值,看余数是否在剩余的数组中,由于数组的查找近似O(1),所以整个算法的时间复杂度可以看作O(n)

代码一:

1
2
3
4
5
6
7
8
9
10
11
12
13
def find(arr,target):
data = {}
for key,value in enumerate(arr):
if value in data:
data[value].append(key)
else:
data[value] = [key]

for key,value in enumerate(arr):
if (target - value) in data:
for key2 in data[target-value]:
if key != key2:
return (key,key2)

这是借用一个字典用于存储数组和下标,然后遍历数组找到差值的坐标返回,虽然性能也是O(n),但相较于下边的代码,简洁度却逊色不少。

代码二:

1
2
3
4
5
6
7
8
def twosumm(numbers,target):
data = {}
if len(numbers)<1:
return False
for i in range(len(numbers)):
if target - numbers[i] in data:
return (data[target-numbers[i]],i)
data[numbers[i]] = i

这是用一个字典存储数组中的数字和下标,每次遍历的时候,查找一下差值是否已经在字典中,如果存在,那么命中,否则接着遍历。

总结: 关键点在于差值的查找,由于字典的查找时间复杂度为O(1),所以只需要遍历一遍数组,整体的算法也就只花费了O(n)

你的支持我的动力