1 / 4思路
Two Sum
思路
一次遍历,用哈希表记录“已经见过的值 → 下标”。对当前 nums[i],先查 target - nums[i] 是否在表里;在就返回两个下标,不在就把当前值写进表。不能先写后查,否则同一个元素可能被用两次。
复杂度
- 时间 O(n):每个元素查一次、写一次。
- 空间 O(n):哈希表最坏存 n 个元素。
代码
- Python
- TypeScript
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 []
function twoSum(nums: number[], target: number): number[] {
const seen = new Map<number, number>();
for (let index = 0; index < nums.length; index += 1) {
const need = target - nums[index];
if (seen.has(need)) return [seen.get(need)!, index];
seen.set(nums[index], index);
}
return [];
}
边界
- 数组长度小于 2:没有答案,返回空。
- 有重复值:哈希表保留最早下标,仍能返回正确的一对。
- 要求返回下标而不是值:不能先排序,排序会丢失原始下标。