Hints

• 水题

---

题面

Difficulty	Time Complexity Limit	Extra-Memory Complexity Limit
Easy	$O(n)$	$-$

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example:

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

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

---

题意

给定一个长为 $n$ 的数组，给定一个整数 $target$ ，求出一个二元组 $(i,\ j),\ i \ne j$ ，满足 $nums_i + nums_j = target$ 。如果有多组解，求出任意一组解即可。

---

题解

暴力枚举的做法很显然，时间复杂度为 $O(n^2)$ 。也容易想到枚举其中一个数然后二分查找另一个数（当然，需要先排序），时间复杂度为 $O(n\log{n})$ 。这两种方法都非常简单，此处不予赘述。

我们维护一个哈希表或者unordered_map，记录数组中每个数值对应的下标，初始为空。我们依次遍历数组中的每个元素，查找表中此时是否有键为 $target - num_i$ 的记录，如果找到则返回答案，否则将 $num_i$ 插入表中。而且问题只需要求出任意一组解，我们甚至不需要考虑哈希冲突的问题。

因为unordered_map是 $O(1)$ 操作的，所以总的时间复杂度为 $O(n)$ 。

---

AC代码

class Solution {
public:
	vector<int> twoSum(vector<int> & nums, int target) {
		// 求解
		unordered_map<int, int> ump;
		for (int i = 0; i < nums.size(); i ++) {
			// 查找
			int val = target - nums[i];
			if (ump.find(val) != ump.end()) {
				return vector<int>({ump[val], i});
			}
			// 插入
			ump[nums[i]] = i;
		}
		// 返回
		return vector<int>({-1, -1});
	}
};

---