[LeetCode] 1. 两数之和 (Two Sum)

发表于 分类于

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

解题思路

使用哈希表存储已遍历的元素及其下标。遍历数组时，对于每个元素，检查 target - nums[i] 是否在哈希表中。

  • 时间复杂度： O(n)
  • 空间复杂度： O(n)

代码实现

1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        hash_map = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in hash_map:
                return [hash_map[complement], i]
            hash_map[num] = i
        return []

总结

哈希表是解决”查找配对”类问题的经典工具，以空间换时间。