两数之和

给定一个整数数组 nums 和一个目标值 target，请找出数组中和等于 target 的两个元素，并返回它们的下标。

约定

• 输入保证有且仅有一个答案。
• 同一个位置的元素不能重复使用两次。
• 返回的下标按升序排列，即 [i, j] 满足 i < j。
• 下标从 0 开始计数。
• 你可以按任意顺序遍历数组，只要返回的下标对正确即可。

输入

• nums：整数数组，长度 2 ≤ nums.length ≤ 10^4，元素取值范围 -10^9 ~ 10^9
• target：整数，取值范围 -10^9 ~ 10^9

输出

长度为 2 的整数数组 [i, j]，满足：

i < j 且 nums[i] + nums[j] == target

示例一

输入：

nums = [2, 7, 11, 15], target = 9

输出：

[0, 1]

解释：nums[0] + nums[1] = 2 + 7 = 9。

示例二

输入：

nums = [3, 2, 4], target = 6

输出：

[1, 2]

示例三

输入：

nums = [3, 3], target = 6

输出：

[0, 1]

解释：两个元素的值可以相同，但必须是不同的两个位置。

提示

• 最直观的做法是两层循环枚举所有位置对，但数组长度到 10^4 时，比较次数约为 10^8，会超过时间限制。
• 换个角度：遍历到 nums[i] 时，你要找的其实是「之前是否出现过 target - nums[i]」。
• 用一个哈希表把「元素值 → 下标」记下来，边遍历边查，就能把查找降到常数时间。

复杂度要求

• 时间复杂度：O(n)，n 为数组长度
• 空间复杂度：O(n)，用于哈希表