两数之和头歌

题目描述：

给定一个整数数组nums 和一个目标值 target，请在数组中找出和为目标值的两个整数。

示例：

nums = [2, 7, 11, 15]
target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

方法一：暴力枚举

最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。

例如：

def twoSum(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

nums = [2, 7, 11, 15]
target = 9
print(twoSum(nums, target))

输出：

[0, 1]

方法二：哈希表

我们可以创建一个哈希表，来帮助快速寻找数组中是否存在目标元素。

例如：

def twoSum(nums, target):
    hash_table = {}
    for i, num in enumerate(nums):
        if target - num in hash_table:
            return [hash_table[target - num], i]
        hash_table[num] = i
    return []

nums = [2, 7, 11, 15]
target = 9
print(twoSum(nums, target))

输出：

[0, 1]

时间复杂度：O(n)。我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间。

空间复杂度：O(n)。所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n 个元素。