题目描述

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

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

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

题解

因为要找到元素对应的位置，很容易想到使用哈希表。将元素的值作为key，元素的位置作为value。

C++代码实现

a) 两遍哈希

1. 建立nums[i] -> i 的哈希表；

2. 遍历哈希表输出答案。

   class Solution {
   
   public:
   
     vector<int> twoSum(vector<int>& nums, int target) {
   
       unordered_map<int, int> record;
   
       for(int i = 0; i < nums.size(); ++i)
   
       {
   
         record[nums[i]] = i;   //建立哈希表
   
      }
   
       for(int i = 0; i < nums.size(); ++i)
   
       {
   
         if(record.find(target - nums[i]) != record.end() && record[target - nums[i]] != i)    //遍历哈希表
   
           return {i, record[target -nums[i]]};
   
       }
   
       return {};
   
   };
   

   b) 一遍哈希

   在建立哈希表的同时寻找答案。

   class Solution {
   public:
       vector<int> twoSum(vector<int>& nums, int target) {      
           //一遍hash，在建立哈希表的同时寻找答案
           unordered_map<int, int> record;
           for(int i = 0; i < nums.size(); ++i)
           {
               if(record.find(target - nums[i]) != record.end())
               {
                   return {record[target - nums[i]], i};
               }
               record[nums[i]] = i;
           }
           return {};
       }
   };