1. 两数之和 Two Sum
题目简述
给定一个整数数组 nums 和一个整数目标值 target，
请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。
我的思路
一开始我想到的是暴力解法：两层循环，把每一对数字都加起来检查一遍，
时间复杂度是 O(n²)。后来我想到可以用哈希表：遍历数组时，把每个数字存进表里，
同时检查 target - nums[i] 是否已经出现过。这样只需要一次遍历，
时间复杂度降到 O(n)。
我的解法
class Solution:
def twoSum(self, nums: list[int], target: int) -> list[int]:
seen = {} # 记录每个数对应的下标
for i, num in enumerate(nums):
diff = target - num # 需要的另一个数
if diff in seen: # 之前已经出现过
return [seen[diff], i]
seen[num] = i # 先存起来，供后面的数查找
return []function twoSum(nums, target) {
const seen = {}; // key: 数字, value: 下标
for (let i = 0; i < nums.length; i++) {
const diff = target - nums[i]; // 需要的另一个数
if (diff in seen) {
return [seen[diff], i];
}
seen[nums[i]] = i; // 先存起来，供后面的数查找
}
return [];
}复杂度分析
- 时间复杂度：O(n) —— 只需遍历一次数组
- 空间复杂度：O(n) —— 哈希表最多存 n 个数