本文共 1888 字，大约阅读时间需要 6 分钟。

1. 题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

2. 解法1

先说一个时间复杂度为O(N*N)的解法，核心思想就是：给定两个下标i，j，然后对每个i都匹配一遍nums[j]，j的变化范围是0~N-1。毫无疑问，这是非常不理想的解法。

代码如下：

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

3. 解法2

第一种解法之所以耗时，是因为对于每一个i，都要遍历所有去寻找一个 target - nums[i]，因此我们可以想到用哈希表，如果target - nums[i]存在，则找出其索引！用空间换时间，毕竟，现在内存硬件都相对便宜了很多；而对于无意义的等待，大多数人是接受不了的，哈哈哈。

利用C++的哈希表（unordered_map），可以将时间复杂度将至O(N)，空间复杂度为O(N)。所以我们需要创建一个哈希表，对于每一个i，首先查询哈希表中是否存在 target - nums[i]，然后将nums[i]插入到哈希表中，保证不会与自己匹配。

#include 
   
        vector
    
      twoSum(vector
     
      & nums, int target) {        int size = nums.size();	    unordered_map
      
        mp;        for(int i = 0; i < size; i++){            auto it = mp.find(target - nums[i])            if(it != mp.cend())                return {it -> second, i};            mp[nums[i]] = i;   // 如果没有的话，就将 nums[i], i 作为一对存入哈希表中，注意，这里key是数组值，value是下标        }        return {};}
      
     
    
   

3. ordered_map常用知识

unordered_map作为C++库中的哈希表，肩负重任！

1. 迭代器

   unordered_map
        
         ::iterator it;(*it).first;             // the key value (of type Key)(*it).second;            // the mapped value (of type T)(*it);                   // the "element value" (of type pair
         
          ) 或者：it->first;               // same as (*it).first   (the key value)it->second;              // same as (*it).second  (the mapped value)
         
        

2. 方法：

   find 　　　　　　通过给定主键查找元素,没找到：返回unordered_map::endat  　 　　　    访问元素 ...             ...

转载地址：http://wqwki.baihongyu.com/