两数之和

🟢 Easy · 🏷️ 数组、哈希表 · LeetCode#1

📖 题目

给定整数数组 nums 和目标值 target，找出和为 target 的两个数，返回它们的下标。

例如 nums = [2,7,11,15]，target = 9，输出 [0,1]，因为 nums[0] + nums[1] = 2 + 7 = 9。

暴力解法两层循环枚举所有数对，时间复杂度 O(n²)。

🔑 哈希表

哈希表用一个函数把 key 直接映射到数组下标，查找不需要遍历，只有常数次运算，时间复杂度 O(1)。

哈希冲突有两种处理策略：

策略	存储方式	优点	代价
链地址法（chaining）	每个槽挂一个链表，冲突元素追加进去	实现简单	全部撞同一槽时退化成 O(n)
开放寻址法（open addressing）	冲突时探测下一个空槽，数据都存在数组里	内存连续、缓存友好	删除要留"墓碑"标记，不能直接清空槽位

CPython 的 dict 用的是开放寻址法。

这道题会用到 Python dict 的两个操作：

"a" in d       # 判断是否存在，O(1)
d["a"] = 1     # 设值，O(1)

💡 思路

用字典记录见过的数字和它的下标。遍历到 num，先看 target - num 是不是已经在字典里——在，两数之和找到了，返回两个下标；不在，把 num 存进字典，继续往下走。

💻 代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}  # 数字 → 下标
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return [seen[complement], i]
            seen[num] = i

时间复杂度 O(n)，空间复杂度 O(n)。