题目：
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, and you may not use the same element twice.
Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
思路：
1.使用multimap存储元素和对应下标
2.对数组进行排序
3.从数组两端寻找目标元素
4.从multimap中查找对应下标
代码：
1 class Solution {
2 public:
3 vector<
int> twoSum(vector<
int>& nums,
int target) {
4 int l =
0;
5 int r = nums.size() -
1;
6 int i =
0;
7 vector<
int>
result;
8 multimap<
int,
int>
m;
9 multimap<
int,
int>
::iterator itmulti;
10 for (vector<
int>::iterator it = nums.begin(); it != nums.end(); it++
) {
11 int temp = *
it;
12 m.insert(make_pair(temp, i++
));
13 }
14 sort(nums.begin(), nums.end());
15 while (l <
r) {
16 if (nums[l] + nums[r] ==
target) {
17 if (nums[l] ==
nums[r]) {
18 for (itmulti =
m.equal_range(nums[l]).first;
19 itmulti !=
m.equal_range(nums[l]).second;
20 itmulti++
) {
21 result.push_back((*
itmulti).second);
22 }
23 }
else {
24 itmulti =
m.equal_range(nums[l]).first;
25 result.push_back((*
itmulti).second);
26 itmulti =
m.equal_range(nums[r]).first;
27 result.push_back((*
itmulti).second);
28 }
29 break;
30 }
else if (nums[l] + nums[r] <
target) {
31 l++
;
32 }
else {
33 r--
;
34 }
35 }
36 return result;
37 }
38 };
转载于:https://www.cnblogs.com/sindy/p/6413852.html
