Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9

Output: index1=1, index2=2

Tags: Array, Hash Table

 

分析：本题容易想到使用双重循环遍历所有可能的组合，如何组合的两个数加起来等于Target，则返回。但是这样会超时。

那么，如何才可以降低算法复杂度呢？使用map。map内部自建一颗红黑树，可以对数据自动排序，正是因为map中数据有序，搜索起来会比较快。

这样，我们只需要单重循环遍历数组，对于每次遍历到的数numbers[i]，我们在map中找有没有存储<Target-numbers[i], 相应index>数据对，这里键为Target-numbers[i]，map排序是依据键值的。如果找到，则返回；如果没有找到，则在map种插入<numbers[i], i+1>作为map新数据对。

这样一来，每次遍历一个元素只需要在map种搜索对应元素，而不是像双重循环中那样，对每个元素都要尝试它后面的所有元素是否可以构成有效组合。

 

c++实现代码：

1 class Solution { 2 public: 3     vector
     
       twoSum(vector
      
        &numbers, int target) { 4         vector
       
         index; 5         map
        
          mp; 6         map
         
          ::iterator iter; 7          8         for (int i = 0; i != numbers.size(); ++i) { 9             iter = mp.find(target - numbers[i]);10             if (iter != mp.end()) {11                 int start = mp.find(target - numbers[i])->second;12                 int end = i + 1;13                 index.push_back(start);14                 index.push_back(end);15                 return index;16             } else {17                     mp.insert(pair
          
           (numbers[i],i+1));18 }19 }20 21 }22 };
          
         
        
       
      
     

代码注释： 

9.//find()函数返回一个迭代器，如果找到返回相应迭代器，如果没找到返回end()返回的迭代器

10.//找到了

11.//iter->first是map数据对的键值，iter->second是数据对的value

13.//vector的插入数据方式

16.//没找到

17.//将当前遍历到的值和相应index+1插入map。也可以通过 mp[numbers[i]] = i + 1 插入，但两者不同，insert是不覆盖，而此法覆盖。