【LeetCode】1. Two Sum

题目：

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.

从给定的一个整数数组中找出两个数，使得它们的和为target，并返回两个数在原数组中的下标

思路：

1. 对数组进行排序，为了方便获取排序后的原下标，采用multimap（map不允许重复的keys值）

multimap不能用 [key] = value的方式来行赋值，但是map可以

2. 用两个游标(i = 0, j = size - 1)分别从数组的两头开始，如果

1) nums[i] + nums[j] > target 大于目标值，则将j往前移一位

2) nums[i] + nums[j] < target 小于目标值，则将i往后移一位

3) nums[i] + nums[j] = target 完成~

 1 class Solution {
 2 public:
 3     vector<int> twoSum(vector<int>& nums, int target) {
 4         int nsize = nums.size();
 5         multimap<int, int> _n_i;
 6         for(int i = 0; i < nsize; i++)
 7             _n_i.insert(pair<int,int>(nums[i], i));
 8             
 9         vector<int> result;
10         multimap<int, int>::iterator _it_begin = _n_i.begin();
11         multimap<int, int>::iterator _it_end = _n_i.end();
12         --_it_end;
13         while(true){
14             int tmp = _it_begin->first + _it_end->first;
15             if(tmp < target)
16                 ++_it_begin;
17             else if(tmp > target)
18                 --_it_end;
19             else{
20                 int i = _it_begin->second;
21                 int j = _it_end->second;
22                 if(i > j){
23                     int _tmp = i;
24                     i = j;
25                     j = _tmp;
26                 }
27                 result.push_back(i);
28                 result.push_back(j);
29                 return result;
30             }
31         }
32     }
33 };