Python面试宝典第1题：两数之和

题目

给定一个整数数组 nums 和一个目标值 target，找出数组中和为目标值的两个数的索引。可以假设每个输入只对应唯一的答案，且同样的元素不能被重复利用。比如：给定 nums = [2, 7, 11, 15] 和 target = 9，返回 [0, 1]，因为 nums[0] + nums[1] = 2 + 7 = 9。

暴力法

暴力法，也称为穷举法，其基本策略是尝试数组中所有可能的数对组合，逐一检查它们的和是否等于目标值。这种方法虽然效率较低，但优点在于直接而简单。使用暴力法求解本题的主要步骤如下。

1、双重循环。使用两个嵌套循环，外层循环遍历数组中的每一个元素，内层循环遍历当前元素之后的所有元素。

2、求和比较。对于内层循环中的每一个元素，计算它与外层循环选定元素的和，并与目标值进行比较。

3、结果输出。一旦找到一组和等于目标值的元素，立即返回它们的索引，因为题目已经假设只有唯一的一组答案。

4、未找到处理。如果遍历完整个数组仍未找到符合条件的数，则返回一个特定的值表示未找到，比如：None 或空列表。

根据上面的算法步骤，我们应当比较容易得出下面的示例代码。

def two_sum_brute_force(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return None

nums = [2, 7, 11, 15]
target = 9
# 输出：[0, 1]
print(two_sum_brute_force(nums, target))

nums = [6, 7, 11, 15]
target = 9
# 输出：None
print(two_sum_brute_force(nums, target))

哈希映射法

哈希映射法，也叫哈希表方法，或哈希查找法，通过利用哈希表来加速查找过程。这种方法的关键在于：遍历数组一次，同时构建一个哈希表，用于存储每个元素的值和其对应的索引。这样，在遍历过程中，可以快速查询是否存在目标和减去当前元素值的元素。使用哈希映射法求解本题的主要步骤如下。

1、初始化哈希表。创建一个空字典，用于存储数组元素值及其索引。

2、遍历数组。遍历输入数组 nums 的每个元素，对于每个元素 num，计算 complement = target - num，即目标值与当前元素的差值。

3、检查 complement 是否在哈希表中。如果存在，说明找到了配对的元素，直接返回这两个元素的索引。若不存在，则将当前元素 num 及其索引存入哈希表。

4、未找到处理。如果遍历完数组仍没有找到解，说明没有满足条件的元素对，则返回None。

根据上面的算法步骤，我们可以得出下面的示例代码。

def two_sum_hashmap(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:
            return [hash_map[complement], i]
        hash_map[num] = i
    return None

nums = [2, 7, 11, 15]
target = 9
# 输出：[0, 1]
print(two_sum_hashmap(nums, target))

nums = [6, 7, 11, 15]
target = 9
# 输出：None
print(two_sum_hashmap(nums, target))

总结

暴力法的时间复杂度为 O(n^2)，其中 n 是数组的长度。这是因为：对于数组中的每个元素，都需要遍历其后的所有元素进行求和比较，相当于遍历两次数组。其空间复杂度为 O(1)，因为它只使用了固定数量的变量，并没有额外使用与输入大小相关的存储空间。尽管暴力法在小规模数据集上可以接受，但在数据量大时效率极低。

哈希映射法的时间复杂度为O(n)，这是因为：每个元素只需要遍历一次数组，并且哈希表的查找操作平均情况下接近O(1)。其空间复杂度同样为O(n)，因为在最坏的情况下，需要将数组中的所有元素都存储到哈希表中。哈希映射法相较于暴力法显著提升了效率，成为解决此类问题的首选策略。