🎯 今日挑战

题目名称: 1. 两数之和
难度: ⭐️
标签: 数组 哈希表
提交次数: 3次（记录调试次数）

🚀 解题历程

💡 初始思路

1
2
3
4
5
6
7
# 暴力解法 - 初版
def twoSum(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

测试用例失败：

  • 输入：nums = [3,3], target = 6
  • 预期输出：[0,1]
  • 实际输出：[0,1] ✅
  • 但时间复杂度 O(n²) 导致在 10^4 数据量时超时 ❌

🔄 优化路径

关键突破：发现哈希表可以实现 O(1) 时间查找补数
实现方案：

  1. 创建空字典存储已遍历数值
  2. 遍历时计算补数（target - current）
  3. 检查补数是否存在于字典
1
2
3
4
5
6
7
# 优化版核心逻辑
seen = {}
for i, num in enumerate(nums):
    complement = target - num
    if complement in seen:
        return [seen[complement], i]
    seen[num] = i

🛑 遇到的坑

  1. 重复元素处理

    • 初始版本处理 nums = [3,3] 时正常，但哈希表方案需要覆盖写入：
      1
      seen[num] = i  # 允许覆盖相同值的最新索引

  2. 索引顺序问题

    • 必须返回 [seen[complement], i] 确保顺序正确

  3. 边界条件

    • 增加空输入校验：
      1
      2
      if not nums:
          return []

🌟 最终实现

✅ 通过代码

1
2
3
4
5
6
7
8
def twoSum(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
    return []