算法题目：两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
示例：
输入：nums = [3,2,4], target = 6
输出：[1,2]
这题有三种解法：
1.利用双重循环暴力破解，时间复杂度为：O(n²)

class Solution {
	public int[] twoSum(int[] nums, int target) {
		for(int i=0;i 
2.将数组先进行排序，再设置首尾指针，首尾递进查找求解时间复杂度为：O(nlogn)
 （下图代码有误，未考虑下标信息）
 
 vector::iterator itBegin = nums.begin();
        vector::iterator itEnd = nums.end();
        sort(itBegin, itEnd);
        itEnd--;
        int numBegin=0;
        int numEnd=nums.size()-1;
        while (true)
        {
            if (*(itBegin)+*(itEnd)==target)
                break;
            else
            {
                if (*(itBegin)+*(itEnd) > target)
                {
                    itEnd--;
                    numEnd--;
                }
                else 
                {
	                numBegin++;
	                itBegin++;
                }
            }
        }
        vector res;
        res.push_back(numBegin);
        res.push_back(numEnd);
        return res;
 
3.使用哈希表求解：复杂度为O(n)
 c++中map有三种分别是std::unordered_map， unordered_multimap，std::map 和std::multimap。其中std::map 和std::multimap 分别是不允许map中有重复key值和允许有重复key，其底层都是基于红黑树实现的，通过二叉树的形式存储查找，其按照元素添加的顺序来存储对象，是有序的，而std::unordered_map， unordered_multimap是基于哈希表实现的，插入元素的位置是根据key值计算得来的，所以是无序的，对于存取值来说unordered_map要比map快不少。
 此题未要求有序，所以可用更快的unordered_map来做，将num数组中的值做为键，将下表存为值进行遍历查找：
 
class Solution {
public:
    vector twoSum(vector& nums, int target) {
        std::unordered_map  map;
        for(int i = 0; i < nums.size(); i++) {
            auto iter = map.find(target - nums[i]);
            if(iter != map.end()) {
                return {iter->second, i};
            }
            map.insert(pair(nums[i], i));
        }
        return {};
    }
};