哈希

哈希

1 两数之和（Two Sum）：leetcode.cn/problems/two-sum/

给定整数数组 nums 和目标值 target，在数组中找出两个数使得它们的和等于 target，并返回这两个数的下标。

• 每种输入只会对应一个答案；
• 同一个元素不能使用两次；
• 下标返回顺序任意。

思路与解答（哈希表）

遍历数组，用哈希表 map 记录已出现的数字及其下标。对当前 num，检查补数 target - num 是否已出现：出现则直接返回两者下标；否则把当前数字加入哈希表。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        map = {}  
        for i, num in enumerate(nums):
            x = target - num
            if x in map:
                return [map[x], i]
            map[num] = i
        return []

复杂度分析

• 时间复杂度：O(n)，每个元素最多入表一次、查表一次（均摊O(1)）。
• 空间复杂度：O(n)，最坏情况下哈希表存储所有元素。