算法分析-两数之和

今天做一个简单算法题：两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。

看到这个题一般会想到双重遍历，两两组合等于 target 就返回下标。但是这样太不够优雅。

我们只需要把遍历过的数放到字典中，将它作为 key、它的下标作为 value。后面遍历的数中，如果在字典里有与它加起来能等于 target 的数，直接返回两者的下标即可。

def twoSum(self, nums: list[int], target: int) -> list[int]:
    seen = dict()
    for i, item in enumerate(nums):
        x = target - item
        if x in seen:
            return [seen[x], i]
        else:
            seen[item] = i

时间复杂度 $O(n)$，空间复杂度最坏情况下要存下 n - 1 个数，所以也是 $O(n)$。