1. 题目

太久没刷力扣都忘了，题目要求返回答案而不是打印答案，一上来评测告诉我自己的结果为null我都懵了。。。

自己第一时间想到的答案

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        ans = []
        length = len(nums)
        for i in range(length):
            for j in range(i+1, length):
                if nums[i]+nums[j] == target: 
                    ans.append(i)
                    ans.append(j)
        
        return ans

显然双层遍历的复杂度为$O(n^2)$，这是不可接受的。

如何改进？

接下来是对代码思路进行改进：当遍历第一个数时，实际上已经在遍历第二个数了（第二个数就是target-num）。所以只需要快速查找第二个数就可以了。如何快速查找第二个数？最快的查找方法就是哈希查找（$O(1)$级别）。只需要在遍历第一个数的时候，同时创建+查找第二个数的哈希表就好了。

改进代码

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 创建用于遍历的索引
        num_dict = {}

        # 枚举遍历第一个数
        for idx1, num1 in enumerate(nums):
            
            num2 = target - num1
            
            # 若第二个数在现有的字典里，则直接返回
            if num2 in num_dict:
                return [num_dict[num2], idx1]

            # 如果不在，添加到字典中便于下一轮查找。
            # 注意key是数值，value是下标，因为我们要查找的是数值对应的下标而不是下标对应的数值
            num_dict[num1] = idx1

反思复盘

1. 可以通过for + enumerate的方法来遍历数组，每轮的遍历对象是idx和num。
2. python哈希字典的查找速度是$O(1)$。