Python算法训练序列
数组与哈希 · Unit 02
← Unit 01
1
LeetCode 1Two Sum · 两数之和
不仅要知道“见过”，
还要记住“它在哪里”。
上一单元用集合回答“是否出现过”。这一单元把集合升级为字典：对当前数 num，计算补数 need = target - num，并在历史映射中寻找它的索引。
LeetCode #1 原题内容
中文转述 · 保留示例、约束与提交签名
题目要求
给定整数数组 nums 和整数 target，返回两个元素的索引，使它们的和等于 target。每组输入恰好有一个有效答案，并且同一个元素不能使用两次；答案顺序不限。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 在这里提交答案
约束
2 ≤ len(nums) ≤ 10000-10⁹ ≤ nums[i], target ≤ 10⁹- 只存在一个有效答案。
示例
nums = [2,7,11,15], target = 9
输出：[0,1]
因为 nums[0] + nums[1] = 9。
输出：[0,1]
因为 nums[0] + nums[1] = 9。
nums = [3,2,4], target = 6
输出：[1,2]
输出：[1,2]
nums = [3,3], target = 6
输出：[0,1]
输出：[0,1]
1. 直接找一对
2. 形成补数
3. 集合升级字典
4. 代码联动
5. 边界迁移
目标和 target
9
历史映射 seen值 → 索引
seen = {}
当前索引 i—
当前 num—
所需 need—
查询结果—
返回值—
补全 LeetCode 提交代码写不出可直接看答案
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen =
for i, num in enumerate(nums):
need =
if :
return
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {}
for i, num in enumerate(nums):
need = target - num
if need in seen:
return [seen[need], i]
seen[num] = i
答案仍然很短，但比 #217 多了一层信息。集合只存“值”；本题必须返回索引，因此使用字典保存
值 → 索引。另外必须先查询 need，再保存当前 num，这样不会把同一个元素使用两次。代码—数组—字典联动可点击任意代码行
1class Solution:
2 def twoSum(self, nums: List[int], target: int) -> List[int]:
3 seen = {}
4 for i, num in enumerate(nums):
5 need = target - num
6 if need in seen:
7 return [seen[need], i]
8 seen[num] = i
点击“下一行”，观察 num、need 和 seen 怎样一起变化。
完成代码联动后进入边界迁移
完成任一条件即可解锁：补全正确、查看答案，或播放完整轨迹。
迁移题：为什么不能先保存，再查询？
输入 nums = [3, 2, 4]、target = 6。如果先执行 seen[num] = i，再判断 need in seen，扫描到第一个 3 时可能错误地把同一个索引使用两次。请写出正确函数。
本单元形成的算法Skill
面对“两数满足某个目标关系”时，把当前值转换为它所需要的历史补数：need = target - num。字典 seen 保存此前元素的“值 → 索引”，因此一次查询即可找到配对位置。
LeetCode #1补数 needdict 值→索引先查后存时间 O(n)空间 O(n)
#217 已完成：哈希集合是否出现过
#1 当前：哈希映射出现在哪里
#242 下一单元：频次统计出现多少次
#49 按键分组如何按特征归类