跳到主要内容

1 / 4思路

Two Sum

原题

思路​

一次遍历,用哈希表记录“已经见过的值 → 下标”。对当前 nums[i],先查 target - nums[i] 是否在表里;在就返回两个下标,不在就把当前值写进表。不能先写后查,否则同一个元素可能被用两次。

复杂度​

  • 时间 O(n):每个元素查一次、写一次。
  • 空间 O(n):哈希表最坏存 n 个元素。

代码​

def two_sum(nums: list[int], target: int) -> list[int]:
seen: dict[int, int] = {}
for index, value in enumerate(nums):
need = target - value
if need in seen:
return [seen[need], index]
seen[value] = index
return []

边界​

  • 数组长度小于 2:没有答案,返回空。
  • 有重复值:哈希表保留最早下标,仍能返回正确的一对。
  • 要求返回下标而不是值:不能先排序,排序会丢失原始下标。