1. Two Sum

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 <vector>
 2 #include <map>
 3 using namespace std;
 4 class Solution {
 5 public:
 6     vector<int> twoSum(vector<int>& nums, int target) {
 7         std::multimap<int, int> idx2Num;
 8         std::vector<int>::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<int> numsSorted;    
17         std::multimap<int, int>::iterator itMap_Fir = idx2Num.begin();
18         std::multimap<int, int>::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             else
29             {
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 };

4. 反思

本算法对数组进行排序采用了取巧的方法，即使用多重map。

若不用map，对Vector进行排序可采用：

方法1：std::sort(nums.begin(), nums.end());//需引入#include <algorithm>
方法2：自己写排序函数