两数之和（Two Sum）

两数之和

题目描述

https://leetcode.cn/problems/two-sum/

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

解题思路

核心观察

对于每个元素 nums[i]，我们需要查找是否存在另一个数 nums[j] 使得 nums[i] + nums[j] == target，即 target - nums[i]。

算法步骤

1. 使用哈希表存储已遍历过的元素及其下标
2. 遍历数组，对每个元素 num，检查 target - num 是否在哈希表中
3. 如果存在，则返回对应下标和当前下标
4. 否则将当前元素及其下标存入哈希表

代码实现

n = int(input())
nums = [int(x) for x in input().split()]
target = int(input())

d = {}
for i, num in enumerate(nums):
    if target - num in d:
        print(d[target - num], i)
        break
    d[num] = i

代码解析

• d 字典：键为数组元素值，值为对应的下标
• target - num：需要匹配的另一个数
• 遍历过程中，先检查是否已存在匹配的数，再将当前数存入哈希表，确保不会使用两次相同的元素

时间复杂度

• 遍历数组：O(n)
• 哈希表查找：O(1)
• 总计：O(n)