给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解题思路1（暴力法）：使用两层循环进行查找匹配，每次都循环的是整个列表，效率比较低。
LeetCode中提交执行结果：超出时间限制。
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(len(nums)):
if target == nums[i] + nums[j] and i != j:
return [i, j]
else:
continue
return None
print(Solution().twoSum([5, 7, 5, 11], 10))
print(Solution().twoSum([9, 7, 3, 11], 18))
print(Solution().twoSum([25, 16, 13, 18, 8, 10], 23))
print(Solution().twoSum([7, 1, 6, 12, 0], 14))
运行结果：
[0, 2]
[1, 3]
[2, 5]
None
解题思路2（暴力法优化版）：使用两层循环进行查找匹配，第二层只循环第一层还未循环的列表元素，效率比思路1高些。
LeetCode中提交执行结果：超出时间限制。
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if target == nums[i] + nums[j]:
return [i, j]
else:
continue
return None
print(Solution().twoSum([5, 7, 5, 11], 10))
print(Solution().twoSum([9, 7, 3, 11], 18))
print(Solution().twoSum([25, 16, 13, 18, 8, 10], 23))
print(Solution().twoSum([7, 1, 6, 12, 0], 14))
运行结果：
[0, 2]
[1, 3]
[2, 5]
None
解题思路3：通过单循环，依次计算出列表中每个元素与target的差值（target-nums[i]），并判断该值（target-nums[i]）是否在列表（仅查找还未循环的列表元素）中，如果在，就通过列表的index()方法获取该值的索引值，如果不在，就继续循环，直到循环完整个列表。
需要注意：在通过index()方法获取索引值时，需要考虑列表中存在相同元素的情况。
LeetCode中提交执行结果-执行用时：1336 ms，内存消耗：14.2 MB。
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
num = target - nums[i]
if num in nums[i+1:len(nums)]:
return [i, nums[i+1:len(nums)].index(num)+ i + 1]
else:
continue
return None
print(Solution().twoSum([5, 7, 5, 11], 10))
print(Solution().twoSum([9, 7, 3, 11], 18))
print(Solution().twoSum([25, 16, 13, 18, 8, 10], 23))
print(Solution().twoSum([7, 1, 6, 12, 0], 14))
运行结果：
[0, 2]
[1, 3]
[2, 5]
None
解题思路4（哈希表法）：通过迭代将元素添加到哈希表（使用字典模拟哈希表）中，同时我们比较该元素的对应元素是否已经存在于哈希表中，如果存在，我们直接返回答案。
LeetCode中提交执行结果-执行用时：36 ms，内存消耗：14.8 MB。
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for index, value in enumerate(nums):
if target - value in hashmap:
return [hashmap[target - value], index]
else:
hashmap[value] = index
print(Solution().twoSum([5, 7, 5, 11], 10))
print(Solution().twoSum([9, 7, 3, 11], 18))
print(Solution().twoSum([25, 16, 13, 18, 8, 10], 23))
print(Solution().twoSum([7, 1, 6, 12, 0], 14))
运行结果：
[0, 2]
[1, 3]
[2, 5]
None
进阶需求（列表中存在多对满足要求的值）：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
注意：不能重复利用这个数组中同样的元素。
示例:
给定 nums = [5, 16, 12, 14, 19, 8, 10, 12], target = 24
因为 nums[0] + nums[4] = 5 + 19 = 24，nums[1] + nums[5] = 16 + 8 = 24，nums[2] + nums[7] = 12 + 12 = 24，nums[3] + nums[6] = 14 + 10 = 24。
所以返回 [[0, 4], [1, 5], [3, 6], [2, 7]]
解题思路1：通过单循环，依次计算出列表中每个元素与target的差值（target-nums[i]），并判断该值（target-nums[i]）是否在列表（仅查找还未循环的列表元素）中，如果在，就通过列表的index()方法获取该值的索引值，如果不在，就继续循环，直到循环完整个列表。
需要注意：在通过index()方法获取索引值时，需要考虑列表中存在相同元素的情况。
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
res_list = []
for i in range(len(nums)):
num = target - nums[i]
if num in nums[i+1: len(nums)]:
res_list.append([i, nums[i+1: len(nums)].index(num)+ i + 1])
else:
continue
return res_list
print(Solution().twoSum([5, 7, 5, 11], 10))
print(Solution().twoSum([9, 7, 3, 2], 9))
print(Solution().twoSum([5, 16, 12, 14, 19, 8, 10, 12], 24))
print(Solution().twoSum([7, 1, 6, 12, 0], 14))
运行结果：
[[0, 2]]
[[1, 3]]
[[0, 4], [1, 5], [2, 7], [3, 6]]
[]
解题思路2（哈希表法）：通过迭代将元素添加到哈希表（使用字典模拟哈希表）中，同时我们比较该元素的对应元素是否已经存在于哈希表中，如果存在，我们直接返回答案。
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
res_list = []
for index, value in enumerate(nums):
if target - value in hashmap:
res_list.append([hashmap[target - value], index])
else:
hashmap[value] = index
return res_list
print(Solution().twoSum([5, 7, 5, 11], 10))
print(Solution().twoSum([9, 7, 3, 2], 9))
print(Solution().twoSum([5, 16, 12, 14, 19, 8, 10, 12], 24))
print(Solution().twoSum([7, 1, 6, 12, 0], 14))
运行结果：
[[0, 2]]
[[1, 3]]
[[0, 4], [1, 5], [3, 6], [2, 7]]
[]
网友评论