Description
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].
Solutions
终于要开始准备刷题了,一看到这个题目当然第一个想法就是看用什么语言了,毕竟平时写代码不是很多,而且一般用 Python 的情况平凡一些,于是还是不要打击信心尝试用 C++,想着还是先弄熟一门语言后再开始搞定另外一门吧。
看到这道题,一般人都很容易想到暴力求解法,能达到 $O(n^2)$ 的时间复杂度,这当然在面试中是不太能博得面试官的芳心的。
1. Brute Force
直接两层 for 循环来找对应的数值对,此时 Time Complexity 是 $O(n^2)$,Space Complexity 是 $O(1)$,总共耗时高达 4332 ms。
# Time: O(n^2)
# Space: O(1)
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# boundary conditions
if len(nums) <= 1:
return [-1, -1]
for i in range(len(nums)-1):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return [-1, -1]
同样是 Brute Force 的方法,但是只是调用了 Python 的 index 来定位也能有一点速度上的提升,以下代码在平台上用时 1380 ms。同样时间复杂度是 $O(n^2)$,空间复杂度是 $\mathcal{O}(n)$。
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if len(nums) <= 1:
return [-1, -1]
dicts = dict(zip(range(len(nums)), nums))
for key, value in dicts.iteritems():
res = target - value
if res in dicts.values() and key != dicts.values().index(res):
return [key, dicts.values().index(res)]
return [-1, -1]
2. One-pass Hash Table
对照暴力求解的方式是遍历一个数就扫描所有的互补数据选,那么我们可以将问题分解一下,首先遍历一遍所有的数字这是必不可少的,那么我们可以做文章的只有在找对应的互补数据的情况下了。为了加速搜索,我们一般会牺牲一点空间复杂度来换取较低的时间复杂度,于是我们用 Hash(即 Python 中的 dict)。如果我们先单独遍历一遍数据得到所有数据的互补数据并存到 dict 当中会有一个问题,如果发生了冲突就不太好存对应的位置了。于是就想到能不能一边遍历数据时一遍存当前数据的互补数据,因为即使有重复,我们只需要前面一个数据就好了,这里不用考虑重复组合的情况。那么我们就可以用如下的方式做,并得到了较好的效果 20 ms。
# Time: O(n)
# Space: O(n)
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# boundary conditions
if len(nums) <= 1:
return [-1, -1]
buff_dict = {}
for i in range(len(nums)):
if nums[i] in buff_dict:
return [buff_dict[nums[i]], i]
else:
buff_dict[target - nums[i]] = i
return [-1, -1]