NC61 两数之和

给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。

（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）

数据范围：2leq len(numbers) leq 10^52≤len(numbers)≤105，-10 leq numbers_i leq 10^9−10≤numbersi​≤109，0 leq target leq 10^90≤target≤109

要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)

输入：

[3,2,4],6

复制返回值：

[2,3]

复制说明：

因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以返回[2,3]            

输入：

[20,70,110,150],90

复制返回值：

[1,2]

复制说明：

20+70=90     

方法：哈希表

C++中使用STL的hashmap(常用操作)_sinat_36413257的博客-CSDN博客_c++ hashmap使用发现网上关于hashmap及map相关简单的操作内容较少，部分博客内容比较复杂不易理解，这里特意分享一个简单的教程。1.at()：根据Key值查找容器内元素，并返回map元素的引用。e.g.#include #include #include

注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)O(N) 降低到 O(1)O(1)。

这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:
    
    vector twoSum(vector& nums, int target) {
        // write code here
        unordered_map map;//无排序的map
        for(int i = 0; i < nums.size(); i++){
            auto index = map.find(target - nums[i]);//查找元素，值
            if(index!= map.end())
                return{index->second+1,i+1};//first值，second索引
            map[nums[i]]=i;//map赋值，值+索引
        }
        return{};
    }
};