Leetcode OJ: Two Sum

 1 class Solution {
 2 private:
 3     // 归并时用到的buffer
 4     vector<int> buffer;
 5     vector<size_t> index_buffer;
 6     // 用于找回排序后的原index
 7     vector<size_t> indexes;
 8 
 9 public:
10     // 归并，注意index也需要进行对应的调整
11     void mergeSort(vector<int>& numbers, size_t begin, size_t end) {
12         if (end - begin <= 1)
13             return;
14         size_t i = begin, j = end, mid = begin + ((end - begin) >> 1);
15         mergeSort(numbers, begin, mid);
16         mergeSort(numbers, mid, end);
17         int k = begin;
18         j = mid;
19         while (i < mid || j < end) {
20             if (j >= end || (i < mid && numbers[i] < numbers[j])) {
21                 buffer[k] = numbers[i];
22                 index_buffer[k] = indexes[i];
23                 k++;
24                 i++;
25             }else {
26                 buffer[k] = numbers[j];
27                 index_buffer[k] = indexes[j];
28                 k++;
29                 j++;
30             }
31         }
32         for (i = begin; i < end; ++i) {
33             numbers[i] = buffer[i];
34             indexes[i] = index_buffer[i];
35         }
36     }
37     
38     size_t search(vector<int>& numbers, size_t begin, size_t end, int target) {
39         size_t mid;
40         while (begin < end) {
41             mid = begin + ((end - begin) >> 1);
42             if (numbers[mid] < target) {
43                 begin = mid + 1;
44             } else if (numbers[mid] > target) {
45                 end = mid;
46             } else
47                 break;
48         }
49         if (begin >= end) {
50             return end;
51         }
52         return mid;
53     }
54 
55     vector<int> twoSum(vector<int> &numbers, int target) {
56         vector<int> ret;
57         if (numbers.empty())
58             return ret;
59         int size = numbers.size();
60         // 初始化index与buffer
61         buffer.assign(size, 0);
62         indexes.assign(size, 0);
63         for (int i = 0; i < size; ++i) {
64             indexes[i] = i + 1;
65         }
66         index_buffer.assign(size, 0);
67         
68         // 归并排序
69         mergeSort(numbers, 0, size);
70         
71         size_t i = 0, j = size - 1;
72         while (i < j) {
73             int sum = numbers[i] + numbers[j];
74             if (sum == target) {
75                 ret.push_back(min(indexes[i], indexes[j]));
76                 ret.push_back(max(indexes[i], indexes[j]));
77                 break;
78             } else if (sum > target) {
79                 size_t tmp = search(numbers, i + 1, j, target - numbers[i]);
80                 // 查找j与下一个的值是否相等，不相等则左移一位
81                 while (numbers[tmp] == numbers[j])
82                     tmp--;
83                 j = tmp;
84             } else {
85                 size_t tmp = search(numbers, i + 1, j, target - numbers[j]);
86                 // 查找i与下一个的值是否相等，不相等则右移一位
87                 while (numbers[tmp] == numbers[i])
88                     tmp++;
89                 i = tmp;
90             }
91         }
92         return ret;
93     }
94 };