题目描述
给定一个整型数组，在数组中找出两个数使这两个数的和为给定数，从小到大输出这两个数在数组中的位置（我们可以假定输出结果只有一个）。例如，输入：N={1,4,8,20}, target=12，输出：index_1=2, index_2=3
方案一
描述
利用C++中的vector和unordered_map尽可能提升程序的运行效率，节约空间，并找出最后的结果。首先回顾一下vector和unordered_map的用法。
vector
vector是C++中的一种数据结构，更确切的说是一个类，相当于一个动态的数组，当一个程序员无法知道自己需要的数组规模有多大时，用其来解决问题已达到最大节约空间的目的。使用vector必须在开头加上#include<vector>，声明一个int向量代替一维数组: vector <int> a;，用vector代替二维数组，只需要声明一个地址的向量:vector <int *> a;，同理多维数组也是如此。下面看vector详细的函数实现功能：
1.push_back 在数组的最后添加一个数据
2.pop_back 去掉数组的最后一个数据
3.at 得到编号位置的数据
4.begin 得到数组头的指针
5.end 得到数组的最后一个单元+1的指针
6.front 得到数组头的引用
7.back 得到数组的最后一个单元的引用
8.max_size 得到vector最大可以是多大
9.capacity 当前vector分配的大小，b.容器已经分配的内存最多可以容纳多少个元素
10.size 当前使用数据的大小，a.容器中有多少个元素，而不是容器为了容纳这些元素分配了多少内存
11.resize 改变当前使用数据的大小，如果它比当前使用的大，者填充默认值，c.强制把容器改为容纳n各元素，如果n小于当前大小，容器尾部元素被销毁，如果n大于当前容量，在元素加入之前会发生重新分配，如果n大于当前大小，新默认构造的元素会添加到容器尾部
12.reserve 改变当前vecotr所分配空间的大小，d.强制把容器的容量改为n，如果n小于当前大小，这个调用什么都不做，否则会强制进行一次重新分配
13.erase 删除指针指向的数据项
14.clear 清空当前的vector
15.rbegin 将vector反转后的开始指针返回(其实就是原来的end-1)
16.rend 将vector反转构的结束指针返回(其实就是原来的begin-1)
17.empty 判断vector是否为空
18.swap 与另一个vector交换数据
2.pop_back 去掉数组的最后一个数据
3.at 得到编号位置的数据
4.begin 得到数组头的指针
5.end 得到数组的最后一个单元+1的指针
6.front 得到数组头的引用
7.back 得到数组的最后一个单元的引用
8.max_size 得到vector最大可以是多大
9.capacity 当前vector分配的大小，b.容器已经分配的内存最多可以容纳多少个元素
10.size 当前使用数据的大小，a.容器中有多少个元素，而不是容器为了容纳这些元素分配了多少内存
11.resize 改变当前使用数据的大小，如果它比当前使用的大，者填充默认值，c.强制把容器改为容纳n各元素，如果n小于当前大小，容器尾部元素被销毁，如果n大于当前容量，在元素加入之前会发生重新分配，如果n大于当前大小，新默认构造的元素会添加到容器尾部
12.reserve 改变当前vecotr所分配空间的大小，d.强制把容器的容量改为n，如果n小于当前大小，这个调用什么都不做，否则会强制进行一次重新分配
13.erase 删除指针指向的数据项
14.clear 清空当前的vector
15.rbegin 将vector反转后的开始指针返回(其实就是原来的end-1)
16.rend 将vector反转构的结束指针返回(其实就是原来的begin-1)
17.empty 判断vector是否为空
18.swap 与另一个vector交换数据
具体用法：
#include <vector>
using namespace std
vector<int> a;
a.clear();//移除容器中的所有数据
a.empty();//判断容器是否为空
a.erase(pos);//删除pos位置的数据
a.erase(begin,end);//删除[begin,end]区间的数据
a.front();//传回第一个数据
a.insert(pos,elem);//在pos位置插入一个elem拷贝
a.pop_back(elem);//删除最后一个数据
a.push_back(elem);//在尾部加入一个数据
a.resize(num);//重新设置该容器的大小
a.size();//返回容器中实际数据的个数
a.begin();//返回指向容器第一个元素的迭代器
a.end();//返回指向容器的最后一个元素的迭代器
unordered_map
unordered_map类似于map，不同的是unordered_map不会根据key的大小进行排序，存储时是根据key的hash值判断元素是否相同，即unordered_map内部元素是无序的，而map中的元素是按照二叉搜索树存储，进行中序遍历会得到有序遍历。所以使用时map的key需要定义operator<。而unordered_map需要定义hash_value函数并且重载operator==。但是很多系统内置的数据类型都自带这些，那么如果是自定义类型，那么就需要自己重载operator<或者hash_value()了。
1. 运行效率：unordered_map高，map效率较低，但是提供了稳定效率和有序的序列
2.内存占用：map内存占用略低，unordered_map较高，而且是线性成比例的
3.选用：无需容器，快速查找删除，不担心略高的内存时用unordered_map。有序容器稳定查找删除效率。内存很在意时用map
核心代码
vector<int> TWOSUN::towSum(vector<int>& array, int target)
{
unordered_map<int, int> hash;
//key是数组的数字，value是数组的索引
vector<int> result;
for (int i = 0; i < array.size(); i++)
{
int numToFind = target - array[i];
if (hash.find(numToFind) != hash.end())
{
result.push_back(hash[numToFind] + 1);
result.push_back(i + 1);
return result;
}
//没有找到
hash[array[i]] = i;
}
return result;
}
方案二
与方案一思想相同的java版本
核心代码如下：
public int[] twoSum_01(int[] array,int target){
int[] result=new int[2];
Map<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=0;i<array.length;i++)
{
if(map.containsKey(target-array[i])){
result[0]=map.get(target-array[i]);
result[1]=i+1;
return result;
}
map.put(array[i],i+1);
}
return result;
}
方案三
思想不同于前两者，而是将每一个target-array[i]存到Hashmap中，核心代码如下：
public int[] twoSum_02(int[] array,int target){
HashMap<Integer,Integer> tracker=new HashMap<Integer,Integer>();
int len=array.length;
for(int i=0;i<len;i++)
{
if(tracker.containsKey(array[i])){
int left=tracker.get(array[i]);
return new int[]{left+1,i+1};
}else{
tracker.put(target-array[i],i);
}
}
return new int[2];
}