1. 问题描述

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example:

Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].

UPDATE (2016/2/13):

The return format had been changed to zero-based indices. Please read the above updated description carefully.

Tags： Array Hash Table

Similar Problems： (M) 3Sum (M) 4Sum (M) Two Sum II - Input array is sorted (E) Two Sum III - Data structure design

2. 解答思路

2.1. 先思考

合法性判断：数组是否为空、数组元素个数是否>=2、target>=0?（想多了，因为题目说You may assume that each input would have exactly one solution.）

数组是否排序？（why这样想? 因为如果是排序数组，只需从头、尾分别向中间靠拢便可找到答案）

数组中是否含有重复的数？（why这样想? 考虑到是个整数数组、且下标位置也是整数，且要进行排序，而map内部本身就是按序存储。若不重复，可用map；若重复，可用multimap）

注意：返回的不是找到的数，而是数的位置，故排序前，需保存下各个数字在数组中的次序

2.2. 算法

先对数组进行排序，设为numsSorted

令pFir指向排序后的数组的头，pSec指向排序后的数组尾部，sum = nutmsSorted[pFir] + numsSorted[pSec];

若sum < target，则pFir++；若sum > target，则pSec--；若sum == target，则返回pFir，pSec.

3. 代码

1 #include 
     
       2 #include 
       3 using namespace std; 4 class Solution { 5 public: 6     vector
       
         twoSum(vector
        
         & nums, int target) { 7         std::multimap
         
           idx2Num; 8         std::vector
          
           ::iterator itVec = nums.begin(); 9 int idx = 0;10 while (itVec != nums.end())11 {12 idx2Num.insert(std::make_pair(*itVec, idx));13 idx++;14 itVec++;15 }16 std::vector
           
             numsSorted; 17 std::multimap
            
             ::iterator itMap_Fir = idx2Num.begin();18 std::multimap
             
              ::iterator itMap_Sec = idx2Num.end();19 itMap_Sec--;20 21 int sum = itMap_Fir->first + itMap_Sec->first;22 while (sum != target)23 {24 if (sum > target)25 {26 itMap_Sec--;27 }28 else29 {30 itMap_Fir++;31 }32 sum = itMap_Fir->first + itMap_Sec->first;33 }34 numsSorted.push_back(itMap_Fir->second);35 numsSorted.push_back(itMap_Sec->second);36 return numsSorted;37 38 }39 };