經(jīng)典的Two Sum問(wèn)題
題目如下
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].
第一種解法 利用散列表
時(shí)間復(fù)雜度O(n)佩谷，空間復(fù)雜度O(n)
解題思路：
比較直接的解題思路敛纲，遍歷數(shù)組的所有元素x充包，查找是否有值匹配target - x登馒。利用散列表查找時(shí)間復(fù)雜度為O(1)
我們可以將查找匹配值的時(shí)間復(fù)雜度下降到O(n)啥寇，相應(yīng)的，因?yàn)槲覀兘⒂成浔砝良钥臻g復(fù)雜度提升到了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
第二種解法 暴力算法
時(shí)間復(fù)雜度O(n**2)爬虱，空間復(fù)雜度O(n)
解題思路，沒(méi)啥好說(shuō)的秉溉。
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
