1. 两数之和

题目链接：国际版，国内版
公司：Meta

题目描述

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

思路

Two-sum 算是 LeetCode 中最出名的一道题了，作为网站中的第一题，尽管其难度为 easy，却也让很多第一次接触 LeetCode 的人败下阵来。

首先简单总结一下题意，就是给一个整数列表和一个目标整数，问该列表中哪两个数的和等于这个目标数，返回这两个数的下标作为结果。我们很容易想到暴力算法，通过嵌套循环来枚举所有可能最后得到结果。这样做的时间复杂度为 O(N^2)，不算最优解。

优化的思路其实有些脑筋急转弯的意味：因为题目中明确规定了是两数之和，而我们还知道目标数 target 是多少，因此对于当前扫描到的数字 num，我们只需要在列表中找 target - num 就可以了。由于最终要返回的是数组下标，因此我们需要借助 HashMap 来存储 num 和 index 的对应关系。这样一来，我们只需要一次扫描就可以得到答案，时间复杂度优化为 O(N)。因为需要一个额外的 HashMap，因此空间复杂度为 O(N)。

代码参考

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # T: O(n), S: O(n)
        num_idx = {}
        for i, num in enumerate(nums):
            if target - num in num_idx:
                return [num_idx[target - num], i]
            num_idx[num] = i