建设一个用教育网站,深圳网站设计 制作元,济南网站开发薪酬,班服定制网站题目 给定一个整数数组 nums 和一个目标值 target#xff0c;找出数组中和为目标值的两个数的索引。可以假设每个输入只对应唯一的答案#xff0c;且同样的元素不能被重复利用。比如#xff1a;给定 nums [2, 7, 11, 15] 和 target 9#xff0c;返回 [0, 1]#xff0c;因…题目 给定一个整数数组 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 Nonenums [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 - numif complement in hash_map:return [hash_map[complement], i]hash_map[num] ireturn Nonenums [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)因为在最坏的情况下需要将数组中的所有元素都存储到哈希表中。哈希映射法相较于暴力法显著提升了效率成为解决此类问题的首选策略。 如果想阅读最新的文章或者有技术问题需要交流和沟通可搜索并关注微信公众号“希望睿智”。
