# 非法输入检查
if not nums:
    return []
if k < 0 or k > len(nums):
    raise ValueError(f"k={k} out of valid range [0, {len(nums)}]")

## 测试
...

## 生产实践
...

题目理解

输入：

• - 数据类型：整数数组 nums 和目标值 target
• 输入规模：数组长度 n，未明确给出范围，但需考虑性能
• 约束：数组元素为整数，可能有重复，未排序

输出：

• - 返回两个下标（索引），使对应元素之和等于目标值
• 假设有且仅有一个有效解

核心问题：

• - 在数组中找出两个不同位置的元素，使其和等于给定目标值，并返回它们的索引

---

解题思路

暴力解

暴力思路：遍历所有可能的元素对，检查它们的和是否等于目标值。
时间复杂度：O(n²)
空间复杂度：O(1)

优化分析

暴力解的问题：对于每个元素，都需要遍历剩余元素来查找互补值，导致大量重复查找操作。
优化目标：将查找互补值的时间从 O(n) 降低到 O(1)。
优化依据：可以用哈希表存储已遍历元素的值到索引的映射，实现常数时间查找。

算法选择

选用：哈希表（字典）
原因：

• - 哈希表提供 O(1) 的平均查找时间，解决了暴力解中的查找瓶颈
• 只需一次遍历，边遍历边构建哈希表，空间换时间
• 相比排序+双指针，哈希表方案更直接，且能正确处理未排序数组

---

算法讲解

算法逻辑

整体框架：遍历数组一次，对于每个元素，检查其互补值（target - 当前值）是否已在哈希表中。如果存在，则找到答案；如果不存在，将当前元素及其索引存入哈希表。

关键变量：

• - complementtoindex：字典，存储已遍历元素的值到其索引的映射
• complement：当前元素所需的互补值，即 target - nums[i]

核心循环：

• - 这个循环在维护一个不变量：哈希表中存储的是所有已遍历元素的索引映射
• 每次迭代：计算当前元素的互补值，检查互补值是否在哈希表中
• 如果找到，立即返回结果；否则将当前元素加入哈希表

终止条件：找到互补对时返回两个索引，题目保证有解。

---

代码实现

python
def two_sum(nums: list[int], target: int) -> list[int]:

在数组中找到两个数之和等于目标值，返回它们的下标。

Args:
nums: 整数数组
target: 目标值

Returns:
包含两个下标的列表 [index1, index2]

# 不变量：complementtoindex 存储已遍历元素的值到索引的映射
complementtoindex = {}

for i, num in enumerate(nums):
complement = target - num
# 检查互补值是否已在哈希表中
if complement in complementtoindex:
return [complementtoindex[complement], i]
# 将当前元素加入哈希表
complementtoindex[num] = i

# 题目保证有解，理论上不会执行到这里
return []

---

测试

测试用例

类型	输入	预期输出	说明
正常用例	nums=[2,7,11,15], target=9	[0,1]	标准情况
最小规模

nums=[3,3], target=6 | [0,1] | 两个相同元素 | | 重复元素 | nums=[3,2,4], target=6 | [1,2] | 元素值重复 | | 边界数据 | nums=[1,2,3], target=5 | [1,2] | 末尾两个元素 | | 特殊结构 | nums=[-1,-2,-3], target=-5 | [1,2] | 负数情况 |

测试结果

python

测试代码

test_cases = [
([2, 7, 11, 15], 9, [0, 1]),
([3, 3], 6, [0, 1]),
([3, 2, 4], 6, [1, 2]),
([1, 2, 3], 5, [1, 2]),
([-1, -2, -3], -5, [1, 2]),
]

for nums, target, expected in test_cases:
result = two_sum(nums, target)
assert result == expected, fFailed: nums={nums}, target={target}, expected={expected}, got={result}
print(f✅ nums={nums}, target={target} → {result})

输出：

✅ nums=[2, 7, 11, 15], target=9 → [0, 1]
✅ nums=[3, 3], target=6 → [0, 1]
✅ nums=[3, 2, 4], target=6 → [1, 2]
✅ nums=[1, 2, 3], target=5 → [1, 2]
✅ nums=[-1, -2, -3], target=-5 → [1, 2]

---

生产实践

5.1 Defensive Coding

python
def twosumdefensive(nums: list[int], target: int) -> list[int]:
# 非法输入检查
if not nums:
raise ValueError(Input array is empty)
if len(nums) < 2:
raise ValueError(Input array must have at least 2 elements)

complementtoindex = {}
for i, num in enumerate(nums):
complement = target - num
if complement in complementtoindex:
return [complementtoindex[complement], i]
complementtoindex[num] = i

# 如果无解，返回空列表或抛出异常
return []

5.2 日志（关键路径）

python
import logging

logger = logging.getLogger(name)

def twosumwith_logging(nums: list[int], target: int) -> list[int]:
# 入口：记录输入的关键特征
logger.info(two_sum() called: len(nums)=%d, target=%d, len(nums), target)

if not nums:
logger.warning(Empty input received, returning empty list)
return []

complementtoindex = {}
for i, num in enumerate(nums):
complement = target - num
# 关键决策点：检查互补值
if complement in complementtoindex:
logger.debug(Found pair: nums[%d]=%d + nums[%d]=%d = %d,
complementtoindex[complement], complement, i, num, target)
return [complementtoindex[complement], i]
complementtoindex[num] = i

# 出口：记录结果
logger.info(two_sum() done: no solution found)
return []

5.3 缓存策略

• - 本题中哈希表本身就是缓存，存储已遍历元素的值到索引的映射
• 如果查询频繁（多次调用 two_sum 对不同目标值），可以预计算所有元素对的和并缓存，但空间开销较大

5.4 Scale & Extension 讨论

• - 数据量增大：如果数组非常大（10⁶ 以上），哈希表方案仍然有效，时间复杂度 O(n)，空间复杂度 O(n)
• 多线程/并发：如果多个线程同时查询，需要确保哈希表的线程安全，可以使用 threading.Lock 或 concurrent 模块
• 流式输入：如果数据是流式输入，无法一次性加载，可以边接收数据边处理，哈希表方案天然支持流式处理
• 在线算法：如果需要实时更新（元素动态添加），哈希表方案可以增量更新，每次添加新元素时检查其互补值是否已存在

5.5 工业界实际应用

Redis 数据库：哈希表是 Redis 的核心数据结构之一，用于实现键值对存储、缓存、会话管理等

• - 场景：缓存系统、分布式锁、计数器
• 为什么用哈希表：O(1) 的读写性能，支持高并发访问

数据库索引：哈希索引用于等值查询的快速定位

• - 场景：MySQL 的 Memory 引擎、NoSQL 数据库（如 Cassandra）
• 为什么用哈希表：等值查询场景下，哈希索引比 B+ 树更快

网络路由表：路由器使用哈希表快速查找下一跳地址

• - 场景：IP 路由、负载均衡
• 为什么用哈希表：需要 O(1) 的查找性能来处理大量并发数据包

来源：基于知识推断