[数据结构与算法]2021-08-14

题目描述

给定一个整数数组 【nums】 和一个整数目标值 【target】，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案

示例1

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 

示例2

输入：nums = [3,2,4], target = 6
输出：[1,2]

题解

在此仅分析官方给出的哈系表解法分析， 完整输出代码如下

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
class Solution{
public:
	vector<int> twosum(vector<int>& nums, int target){
		unordered_map<int, int> hashtable;
		for (int i = 0; i < nums.size(); i++){
			auto it = hashtable.find(target - nums[i]);
			if (it!= hashtable.end()){
				return {it->second, i};
			}
			hashtable[nums[i]] = i;
		}
		return {};

	}
};
int main(){
	Solution sol;
	vector<int> position;
	vector<int> arr = {1,2,3,4,5,6,7};
	int target = 7;
	position = sol.twosum(arr, target);
	for (auto i : position){
		cout << i << endl;
	}
	return 0;
}

输出如下：

2,3

代码分析

1. unordered_map容器初始化，

std::unordered_map<typename of KEY, typename of VALUE> VariableName; 

如赋值构造一个含有三个键值对的umap容器：

std::unordered_map<std::string, std::string> umap{
    {"Python教程","http://csdn/python/"},
    {"Java教程","http://csdn/java/"},
    {"Linux教程","http://csdn/linux/"} };

再如拷贝构造一个利用umap拷贝构造一个容器umap2

std::unordered_map<std::string, std::string> umap2(umap);

再如分区拷贝构造一个容器umap3

std::unordered_map<std::string, std::string> umap3(++umap.begin(),umap.end());

umap3内部就包含 umap 容器中除第 1 个键值对外的所有其它键值对. 因此

unordered_map<int, int> hashtable;

就构造一个名为hashtable的unordered_map容器

2. unordered_map容器的主要成员方法
   3. C++ unordered_map迭代器

unordered_map<Key,T>::iterator it;
(*it).first;             // the key value (of type Key)
(*it).second;            // the mapped value (of type T)
(*it);                   // the "element value" (of type pair<const Key,T>)

故it->second返回键， it->first返回值

4. 关键代码分析

{
unordered_map<int, int> hashtable;
	for (int i = 0; i < nums.size(); i++){
		auto it = hashtable.find(target - nums[i]);
		if (it!= hashtable.end()){
			return {it->second, i};
		}
		hashtable[nums[i]] = i;
	}
return {};
}		

其中

auto it = hashtable.find(target - nums[i]);

在进行给定数组的扫描过程中未找到满足要求的键值对时返回hashtable末元素后一个位置的迭代器hashtable.end()， 否则满足if条件，输出所求键值对

if (it!= hashtable.end()){
	return {it->second, i};
}
hashtable[nums[i]] = i;

每次扫描的同时都更新hashtable

hashtable[nums[i]] = i; //更新hashtable

参考文献

1. https://leetcode-cn.com/problems/two-sum/
2. https://blog.csdn.net/ai_faker/article/details/117714959