Leetcode#1 Two Sum

方法I：辅助数据结构

用一个map保存遇到的值和位置，最直观的想法。

遍历numbers，对于每个元素numbers[i]：

如果在map中找到了target-numbers[i]，说明找到了这两个数字，算法结束

否则，将numbers[i]和所在位置i加入map中

时间复杂度O(n)，空间复杂度O(n)

 1 vector<int> twoSum(vector<int> &numbers, int target) {
 2         map<int, int> record;
 3         vector<int> res;
 4         int size = numbers.size();
 5 
 6         for (int i = 0; i < size; i++) {
 7             // 如果找到，先前在map中的数字的索引肯定更小，所以放在前面
 8             if (record.find(target - numbers[i]) != record.end()) {
 9                 res.push_back(record[target - numbers[i]] + 1);
10                 res.push_back(i + 1);
11                 break;
12             }
13             else
14                 record.insert(pair<int, int>(numbers[i], i));
15         }
16 
17         return res;
18 }

方法II：双指针法

1. 先对数组排序

2. 用两个指针（head和tail）分别指向数组的第一个元素和最后一个元素

3. 考察两个指针所指元素的大小关系：

若head + tail = target，说明找到了这两个数字，算法结束
若head + tail < target，head右移一个元素
若head + tail > target，tail左移一个元素

4. 返回3

以上算法可以保证在移动head和tail的时候不会漏掉解，证明如下：

假设存在number[i] + number[j] = target（i < j）。

head在什么情况下可能移动到i的右边？假设head已经移动到了i的右边，即head > i且numbers[head] > numbers[i]，根据算法规则，只有当numbers[head] + numbers[tail] < target时，head才会右移，所以 numbers[tail] < target - numbers[head] < target - numbers[i] = numbers[j]，意味着tail一定出现在j的左边。

那tail在什么情况下可能移动到j的左边？同理，只有当head在i的右边时才可能发生。

因为一开始head在i的左边，tail在j的右边，算法每次只移动head或tail，所以不可能出现某一时刻经过算法移动后，head移动到i的右边而同时tail移动到j的左边的情况。证明结束。

方法II的前提是数组必须是排好序的，但是数组一旦排序之后，原先元素的位置信息就乱了，怎么找到原先对应的位置呢？得要用一个辅助数据结构保存原先的位置，有没有种突然low了一大截的感觉。这道题也出现在了《Cracking the Code》上，双指针法是书上的解法，但是书上那道题并不是问你索引信息，而是要你找到这两个数，在这个题目下用双指针法比较巧妙。

时间复杂度O(n)，空间复杂度O(n)

 1     bool lessp(pair<int, int> &a, pair<int, int> &b) {
 2         return a.first < b.first;
 3     }
 4 
 5     vector<int> twoSum(vector<int> &numbers, int target) {
 6         vector<pair<int, int> > record;
 7         vector<int> res;
 8         int r = numbers.size() - 1;
 9         int l = 0;
10 
11         // 需要额外的数据结构保存位置信息
12         for (int i = 0; i <= r; i++)
13             record.push_back(pair<int, int>(numbers[i], i));
14 
15         sort(record.begin(), record.end(), lessp);
16         while (l < r) {
17             int sum = record[l].first + record[r].first;
18             if (sum == target) {
19                 res.push_back(record[l].second + 1); // 序号得从1开始
20                 res.push_back(record[r].second + 1); // 序号得从1开始
21                 // 结果必须按照从小到大的顺序出现
22                 sort(res.begin(), res.end());
23                 break;
24             }
25             else if (sum > target)
26                 r--;
27             else
28                 l++;
29         }
30 
31         return res;
32     }