两数之和.md

两数之和

题目描述

除了输入的数组是非排好序的状态外，其他与两数之和-输入有序数组一致

---

解题思路

暴力做法

两层循环，不再赘述

---

哈希表

• 使用哈希表存储数组中的元素及其对应的索引，遍历数组，对于每个元素，判断哈希表中是否存在与该元素相加等于目标值的元素，如果存在，则返回两个元素的索引。
• 在 Python 中，集合set的操作，如添加元素add()、删除元素remove()、查找元素是否存在in，这些操作的时间复杂度都是O(1)的，因为它们依赖于哈希表的实现。

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

• 为什么是用哈希表解决问题呢？因为在哈希表中执行下面这个查找语句if target - num in hashmap，时间复杂度是O(1)。原理是，哈希表通过一个哈希函数Hash Function将键（如 3）转换为哈希值（一个整数）当需要查找某一个值时，哈希表首先通过哈希函数计算哈希值，这个计算过程是基于数学运算（如取模运算），在大多数情况下是常数时间操作，无论键的大小如何，计算时间是固定的.
• hashmap[num] = i，num和i的位置不可以交换，因为创建此哈希表的目的是需要在表中查找是否存在值为[target-num]的元素，如果存在，需要返回其对应的索引。
• 时间复杂度O(n),空间复杂度O(n)，以空间换时间。