【题目3】Two sum(LeetCode)
2018-03-17 本文已影响0人
suwi
问题描述
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.
Example
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
问题分析
方法1: 暴力法 (Brute Force)
双重循环遍历数组中所有元素的两两组合，当出现符合的和时返回两个元素的下标。
def TwoSum(nums, target):
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i]+nums[j]==target:
print([i,j])
return [i,j]
print('No two sum solution.')
numbers = [2,7,11,5]
target = 9
TwoSum(numbers, target)
复杂度分析：
- 时间复杂度：O(n2). 对于数组中的每个元素，我们都要循环遍历剩余所有元素，需要消耗O(n)的时间。
- 空间复杂度：O(1).
方法2: 哈希表 (Hash Table)
为了降低时间复杂度，我们需要一种更有效的方法检查数组中是否存在互补元素。如果互补元素存在，我们需要查找它的索引。那么，保持数组中每个元素的映射到其索引的最佳方式是什么？答案是哈希表。
通过哈希表，可以得到“空间换时间”的效果，把原本O(n)的时间复杂度降低到O(1)。哈希表正是为了这个目的而构建的，它支持在“几乎”恒定的时间内快速查找。这里“几乎”的意思是，倘若哈希表中存在重复的键值，则复杂度会上升到O(n)。不过只要正确地构建哈希表，复杂度总是可以固定到O(1)的。
对于本题，我们创建一个临时哈希表，在遍历原数组并把元素一一插入临时表的同时，检查另一个互补元素是否已经在临时表中，若存在则即刻返回相应的数组下标。
def TwoSum(nums, target):
dict = {}
for i in range(len(nums)):
if target-nums[i] in dict:
print([dict[target-nums[i]],i])
return [dict[target-nums[i]],i]
else:
dict[nums[i]] = i
print('No two sum solution.')
numbers = [2,7,11,5]
target = 9
TwoSum(numbers, target)
复杂度分析：
- 时间复杂度：O(n). 我们只遍历一遍包含n个元素的原数组，并且对于每个元素，返回哈希表查找的时间复杂度为O(1)。
- 空间复杂度：O(n).额外的空间要求取决于哈希表中元素的数目，在最坏情况下哈希表中包含n个元素。
