经典的Two Sum问题
题目如下
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].
第一种解法 利用散列表
时间复杂度O(n)，空间复杂度O(n)
解题思路：
比较直接的解题思路，遍历数组的所有元素x，查找是否有值匹配target - x。利用散列表查找时间复杂度为O(1)
我们可以将查找匹配值的时间复杂度下降到O(n)，相应的，因为我们建立映射表，所以空间复杂度提升到了O(n)
def twoSum(nums,target):
result = []
dict1 = {}
for i in range(0,len(nums)):
dict1[nums[i]] = i # build the mapping between the nums elements and its index
for n in range(0,len(nums)):
the_other = target - nums[n]
if the_other in dict1 and dict1[the_other] != n:# make sure we don't find the same value
result.append(n)
result.append(dict1[the_other])
# if we return result outside the loop, we may get duplicate index as we loop through twice the same combinations
return result
第二种解法 暴力算法
时间复杂度O(n**2)，空间复杂度O(n)
解题思路，没啥好说的。
def twoSum(self, nums, target):
result = []
for i in range(0,len(nums)):
mama = target - nums[i]
for j in range(0,len(nums)):
if nums[j] == mama and j != i:
result.append(i)
result.append(j)
return result
