Python高效解决“两数之和”问题（两数之和 python）

任务要求

给定一个整数数组nums和一个目标值target，在该数组中找出“和”为目标值的两个整数，并返回他们的数组下标。例如，nums = [2, 7, 11, 15]，target = 9；nums[0] + nums[1] = 2 + 7 = 9，返回[0, 1]。

任务分析

方法一：暴力枚举法，一种直观的方法，通过双重循环遍历数组中的所有元素对，检查它们的和是否等于目标值。

步骤：

1．遍历数组中的每一个元素i。

2．对于每个元素i，再次遍历数组中i之后的所有元素j。

3．检查nums[i] + nums[j]是否等于target。

4．如果找到符合条件的元素对，则返回它们的下标[i, j]。

5．如果遍历结束后未找到任何符合条件的元素对，则返回空列表。

优点：简单直接，容易理解。需要额外的空间复杂度。

缺点：时间复杂度较高，在处理大规模数据时效率较低。

方法二：哈希表法，通过利用空间换时间的方式，显著提高了查找效率。

步骤：

1．创建一个空字典seen用于存储已经遍历过的元素及其下标。

2．遍历数组中的每一个元素及其下标。

3．对于当前元素num，计算其补数complement = target - num。

4．检查补数是否存在于字典seen中：

• 如果存在，则返回补数对应的下标和当前元素的下标。
• 如果不存在，则将当前元素及其下标存入字典。

5．如果遍历结束后未找到任何符合条件的元素对，则返回空列表。

优点：在处理大规模数据时效率较高，需要额外的空间存储已遍历的元素。

缺点：需要额外的空间来存储字典。

任务实现

方法一：暴力枚举法

def two_sum_brute_force(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
nums = [2, 7, 11, 15]
target = 9
print(two_sum_brute_force(nums, target)) # 输出: [0, 1]
nums = [3, 2, 4]
target = 6
print(two_sum_brute_force(nums, target)) # 输出: [1, 2]
nums = [3, 3]
target = 6
print(two_sum_brute_force(nums, target)) # 输出: [0, 1]
nums = [1, 2]
target = 4
print(two_sum_brute_force(nums, target)) # 输出: []

说明：

• 双重循环：外层循环遍历数组中的每一个元素i，内层循环从i+1开始遍历后续元素j。
• 条件判断：检查nums[i] + nums[j]是否等于target。
• 返回结果：找到符合条件的元素对后立即返回它们的下标；如果遍历结束后未找到，则返回空列表。

方法二：哈希表法

def two_sum_hash_table(nums, target):
seen = {}
for index, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], index]
seen[num] = index
return []
nums = [2, 7, 11, 15]
target = 9
print(two_sum_hash_table(nums, target)) # 输出: [0, 1]
nums = [3, 2, 4]
target = 6
print(two_sum_hash_table(nums, target)) # 输出: [1, 2]
nums = [3, 3]
target = 6
print(two_sum_hash_table(nums, target)) # 输出: [0, 1]
nums = [1, 2]
target = 4
print(two_sum_hash_table(nums, target)) # 输出: []

说明：

• 初始化字典：创建一个空字典seen用于存储已遍历过的元素及其下标。
• 遍历数组：使用enumerate函数同时获取元素及其下标。
• 计算补数：对于当前元素num，计算其补数complement = target - num。
• 检查补数：如果补数存在于字典中，则返回补数对应的下标和当前元素的下标。
• 更新字典：如果补数不存在于字典中，则将当前元素及其下标存入字典。
• 返回结果：遍历结束后未找到符合条件的元素对，则返回空列表。

运行结果

[0, 1]

[1, 2]

[0, 1]

[]

进程已结束，退出代码为 0