【LeetCode】1. Two Sum（两数之和）-unordered_map实现

本题是一下公司的面试题：

 

问题描述：

问题求解：

使用无序容器unordered_map实现：

#include <iostream>
#include <vector>
#include <cassert>
#include <unordered_map>

using namespace std;

// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {

		unordered_map<int, int> record; //record表示元素的下标
		for (int i = 0; i < nums.size(); i++) {

			int complement = target - nums[i];  //complement为补数
			if (record.find(complement) != record.end()) { //在record中查找元素complement
				int res[] = { i, record[complement] }; //将找到的两个元素的下标放到数组res中
				return vector<int>(res, res + 2);  //返回vector
			}

			record[nums[i]] = i; //将元素nums[i]放到record中，并将下标i计为record的value
		}

		throw invalid_argument("the input has no solution");//找不到答案，抛出异常
	}
};


int main() {

	const int nums[] = { 2, 7, 11, 15};
	vector<int> nums_vec(nums, nums + sizeof(nums) / sizeof(int));
	int target = 9;

	vector<int> res = Solution().twoSum(nums_vec, target);
	cout << res[0] << " " << res[1] << endl;

	getchar();
	return 0;
}

 图解：

①当 i = 0时：

②当 i = 1 时：

Reference:

   https://coding.imooc.com/class/chapter/82.html#Anchor