两数之和代码的核心思路是通过哈希表(字典)高效存储和查找补数,实现时间复杂度O(n)的解法。 以下是具体实现方法和优化要点:
-
暴力枚举法(基础版)
双重循环遍历数组,检查每对数字之和是否等于目标值。虽然简单直观,但时间复杂度为O(n²),仅适用于小规模数据。 -
哈希表优化法(推荐)
遍历数组时,用哈希表记录已访问数字及其下标。对于当前数字num
,计算补数target - num
并查询是否存在于哈希表中,若存在则直接返回结果。此方法将查找时间降至O(1),整体效率显著提升。 -
边界条件处理
需考虑重复值、无解情况(如返回空列表或抛出异常),以及输入为非整数或空数组时的健壮性校验。例如,可预先检查数组长度是否≥2。 -
代码示例(Python)
def two_sum(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 []
总结:哈希表法是解决两数之和问题的黄金标准,兼顾效率与可读性。实际应用中可根据语言特性调整实现,如Java使用HashMap
,JavaScript用Map
对象。