Two Sum

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

思路：

先对数组排序，然后用两个指针分别指向数组的头和尾，向中间聚集找结果。因为该题假设有且只有一个结果，所以没有对重复进行判断。

另外由于需要输出的是index，所以用一个结构体保存index和num，然后根据num排序。

代码：

 1     struct Node{
 2         int num;
 3         int index;
 4     };
 5 
 6     vector<int> twoSum(vector<int> &numbers, int target) {
 7         // IMPORTANT: Please reset any member data you declared, as
 8         // the same Solution instance will be reused for each test case.
 9         vector<int> result;
10         vector<Node> nodes;
11         int i,j;
12         int len = numbers.size();
13         for(i = 0; i < len; i++){
14             Node tNode;
15             tNode.num = numbers[i];
16             tNode.index = i+1;
17             nodes.push_back(tNode);
18         }
19         for(i = 0; i < len-1; i++){
20             for(j = 0; j < len-1; j++){
21                 if(nodes[j].num > nodes[j+1].num){
22                     Node tNode = nodes[j];
23                     nodes[j] = nodes[j+1];
24                     nodes[j+1] = tNode;
25                 }
26             }
27         }
28         i = 0;
29         j = len-1;
30         while(i < j){
31             int tmp = nodes[i].num + nodes[j].num;
32             if(tmp < target)
33                 i++;
34             else if(tmp > target)
35                 j--;
36             else{
37                 if(nodes[i].num > nodes[j].num){
38                     result.push_back(nodes[j].index);
39                     result.push_back(nodes[i].index);
40                 }
41                 else{
42                     result.push_back(nodes[i].index);
43                     result.push_back(nodes[j].index);
44                 }
45                 return result;
46             }
47         }
48     }

还有种思路是直接用hashmap，枚举第一个数，找结果与第一个数的差。