利用哈希表高效解决两数之和问题

引言

在编程面试中，寻找数组中两数之和的问题是一个经典问题。本文将介绍如何利用哈希表高效解决这个问题。

问题描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

示例

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]。

输入：nums = [3,2,4], target = 6
输出：[1,2]

输入：nums = [3,3], target = 6
输出：[0,1]

提示

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• 只会存在一个有效答案

解题思路

要解决这个问题，我们可以使用哈希表（字典）来实现。哈希表可以在常数时间内完成插入和查找操作，这使得我们能够高效地找到目标值所需的两个整数。

步骤

1. 初始化哈希表：我们创建一个空的哈希表（字典）来存储数组中的数值及其对应的下标。
2. 遍历数组：我们遍历数组中的每一个元素，并在哈希表中查找是否存在一个数值，使得当前数值与该数值之和等于目标值 target。
3. 检查是否存在目标值：对于每一个元素 num，我们计算 target - num 的值，并检查这个值是否在哈希表中。如果存在，则找到了两个数，它们的和为 target，返回它们的下标。
4. 更新哈希表：如果没有找到，则将当前元素的值和下标存入哈希表中，以便后续元素可以使用。

算法实现

def two_sum(nums, target):
    # 创建一个哈希表来存储数值和下标
    num_to_index = {}
    
    # 遍历数组
    for i, num in enumerate(nums):
        # 计算需要的另一个数值
        complement = target - num
        
        # 检查哈希表中是否存在这个数值
        if complement in num_to_index:
            # 找到目标值，返回下标
            return [num_to_index[complement], i]
        
        # 将当前数值和下标存入哈希表
        num_to_index[num] = i

    # 如果没有找到，返回空列表（题目保证有解，所以这里不会执行）
    return []

# 示例
print(two_sum([2, 7, 11, 15], 9))  # 输出: [0, 1]
print(two_sum([3, 2, 4], 6))       # 输出: [1, 2]
print(two_sum([3, 3], 6))          # 输出: [0, 1]

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。我们只需遍历数组一次，每次查找和插入操作在哈希表中都是常数时间 O(1)。
• 空间复杂度：O(n)，在最坏情况下，哈希表中要存储 n 个元素。

这个算法利用哈希表的高效查找特性，使得我们能够在一次遍历中找到目标值所需的两个数，达到了线性时间复杂度。