leetcode 1 两数之和(哈希)

题目描述：

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这也算是个水题了吧，毕竟暴力O(n)做也能过：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int len=nums.size();
        vector<int> res;
        for(int i=0;i<len;i++)
            for(int j=i+1;j<len;j++)
            {
                if(nums[i]+nums[j]==target)
                {
                    res.push_back(i);
                    res.push_back(j);
                    return res;
                }
            }
        return res;
    }
};

 当然我也希望尝试更加高效的思路，哈希表基本上都没有使用过，这次在题解中看到了一遍哈希的思路觉得很棒。所以下次看到索引和值对应类似的都应该尝试哈希。

先说C++的map怎么用。我甚至找了好几个网站才知道该怎么用，一直在编译器报错。

1.定义：map<int,int> hash;

2.赋值：hash[0]=1;//增加map<0,1>的记录。

3.函数方法：

　　插入：hash.insert(make_pair(0,1));//使用insert的场景是map中有类元，这样迭代查找的代价会比较大，如map<Student,int>这种。

　　查找：hash.find(key);　　hash.count(key);　　//区别在于find返回元素位值，返回iterator，而count则仅返回真假而已

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int len=nums.size();
        vector<int> res;
        unordered_map<int,int> map;//采用unorderedmap比map节省了一些内存。
        for(int i=0;i<len;i++)
        {
            int cur=target-nums[i];
            if(map.count(cur))
            {
                res.push_back(map[cur]);
                res.push_back(i);
                return res;
            }
            map[nums[i]]=i;
        }
        return res;
    }
};