题目：

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]

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

复杂度分析：

• 时间复杂度：
• 空间复杂度：

效率:

暴力解法效率

2. 哈希表法

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

2.1 两遍哈希

我们可以先遍历一遍，构建哈希表，其中元素的值作为key、元素的索引作为value，从而通过哈希表来确定元素在中的索引位置。然后，再次遍历，通过刚刚构建的哈希表确定是否有元素等于。
需要注意的是，题目中说每个数只能用一次，所以一定要在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]]

复杂度分析：

• 时间复杂度：
• 空间复杂度：：哈希表里存放了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

复杂度分析：

• 时间复杂度：
• 空间复杂度：：哈希表里存放了n个元素

效率：
执行时间从0.060s降低到了0.048s。

一遍哈希效率