Leetcode1.两数之和（思路超详细！！！）

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

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

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路1:
暴力法。即对这个整数数组的做双重循环，对数组中每个数均在数组中找一个目标值（compliment=target-num），若找到，返回两数下标，否则继续往下找。
因此，本方法的时间复杂度是O(n2),空间复杂度是O(1)。

思路二：
借助哈希表。因为我们是根据数的值查找对应的下标，一个自然而然的想法是建立数组值及其下标值的hashmap。C++中map的查找时间复杂度是O(1)，因此本方法的时间用量是O(n),空间复杂度也是O(n).

code:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> hashmap;
        vector<int> res;
        for(int i=0;i<nums.size();i++)
        {
            hashmap.insert(pair<int,int>(nums[i],i));//建立值与下标的hashmap
        }
        for(int i=0;i<nums.size();i++)
        {
            int compliment=target-nums[i];
            if(hashmap.find(compliment)!=hashmap.end()&&hashmap.find(compliment)->second!=i)
            {
                res.push_back(i);
                res.push_back(hashmap.find(compliment)->second);
                break;
}
        }
        return res;
    }
};

关于stl map的相关：
https://www.cnblogs.com/empty16/p/6395813.html