给定一个数组和一个目标值,在数组中找到两个数相加等于目标值。假设,数组中只有一对满足条件的数对。并返回这个数对的索引。
比如[3,3,4,1],target=6,数组中3和3相加为6, 所以返回[0,1]
难点:暴力循环容易解决,但是时间复杂度太高。
解决方法:空间换时间,用一个map把时间复杂度从O(n2)减小到O(n)。
# -*- coding: utf-8 -*-
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
"""
时间复杂度太高 n^2
:param nums:
:param target:
:return:
"""
for index, num in enumerate(nums):
for idx, n in enumerate(nums):
if index != idx and num + n == target:
return [index, idx]
def twoSum2(self, nums: List[int], target: int) -> List[int]:
pairs = dict()
for index, num in enumerate(nums):
pairs[num] = index
print(pairs)
for idx, num in enumerate(nums):
value = target - num
if value in pairs and idx != pairs[value]:
return [idx, pairs[value]]
def twoSum3(self, nums: List[int], target: int) -> List[int]:
h = {}
for idx, num in enumerate(nums):
value = target - num
if value in h:
return [idx, h[value]]
else:
h[num] = idx
if __name__ == '__main__':
l = [3, 3, 4, 1, 1]
target = 6
solution = Solution()
result = solution.twoSum2(l, target)
print(result)