题目：

leetcode1题目描述

解法：

1. 暴力解法

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

这是最最容易想到的方法了......先用 $i$ 遍历一遍 $nums$ 中的每一个元素，然后再看 $nums[i]$ 元素与后面的 $nums[j]$ 元素之和是否等于 $target$ 。

复杂度分析：

时间复杂度： $O(n^2)$
空间复杂度： $O(1)$

效率:

暴力解法效率

2. 哈希表法

暴力解法比较慢是因为我们用了两层循环，为了提高效率，我们可以选择“空间换时间”的方法，来降低第二层循环的时间。所以我们选择使用哈希表来降低查找时间。

2.1 两遍哈希

我们可以先遍历一遍 $nums$ ，构建哈希表，其中元素的值作为key、元素的索引作为value，从而通过哈希表来确定元素在 $nums$ 中的索引位置。然后，再次遍历 $nums$ ，通过刚刚构建的哈希表确定是否有元素等于 $target - nums[i]$ 。
需要注意的是，题目中说每个数只能用一次，所以一定要在if语句中加上条件i!=hashdict[diff]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashdict = {num: index for index, num in enumerate(nums)}
        # print(hashdict)
        for i, num in enumerate(nums):
            diff = target - nums[i]
            if diff in hashdict and i!=hashdict[diff]: ##确保选中的是两个不同索引的数
                return [i,hashdict[diff]]

复杂度分析：

时间复杂度： $O(n)$
空间复杂度： $O(n)$ ：哈希表里存放了n个元素

效率:
可以看到，运行时间显著地降低了，从6.3s降低为0.06s。

两遍哈希效率

2.2 一遍哈希

2.1的方法中，哈希表的构建和查找是分开的，我们可以边构建边查找，从而进一步地降低运行时间。

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

复杂度分析：