Careercup

2014-05-06 13:23

原题：

Finding a pair of elements from two sorted lists(or array) for which the sum of the elements is a certain value. Anyway solution that can do better than O(a.length + b.length)?

题目：给定两个有序的数组，如何从两数组中各选出一个元素使得两元素加起来等于某个目标值。

解法：又是这个“Guy”出的题目，此人想要追求优于O(n + m)的算法。这人代码水平不高，我想他对于算法复杂度的上下界也不知道怎么估计吧。我个人认为不太可能更优化了，因为你找的不是一个元素，而是一对。我的解法，是使用两个iterator，一个在A数组头部，一个在B数组尾部。通过A数组后移，B数组前移来调整相加的结果。这样的算法，复杂度就是O(n + m)的。

代码：

 1 // http://www.careercup.com/question?id=6271724635029504
 2 #include <cstdio>
 3 #include <vector>
 4 using namespace std;
 5 
 6 bool twoSortedArraySum(vector<int> &a, vector<int> &b, int target, int &ia, int &ib)
 7 {
 8     int i, j;
 9     int na, nb;
10 
11     na = (int)a.size();
12     nb = (int)b.size();
13 
14     i = 0;
15     j = nb - 1;
16 
17     int sum;
18     while (i <= na - 1 && j >= 0) {
19         sum = a[i] + b[j];
20         if (sum > target) {
21             --j;
22         } else if (sum < target) {
23             ++i;
24         } else {
25             ia = i;
26             ib = j;
27             return true;
28         }
29     }
30     return false;
31 }
32 
33 int main()
34 {
35     vector<int> a, b;
36     int na, nb;
37     int i;
38     int ia, ib;
39     int target;
40     
41     while (scanf("%d%d", &na, &nb) == 2 && (na > 0 && nb > 0)) {
42         a.resize(na);
43         b.resize(nb);
44         for (i = 0; i < na; ++i) {
45             scanf("%d", &a[i]);
46         }
47         for (i = 0; i < nb; ++i) {
48             scanf("%d", &b[i]);
49         }
50         while (scanf("%d", &target) == 1) {
51             ia = ib = -1;
52             if (twoSortedArraySum(a, b, target, ia, ib)) {
53                 printf("%d + %d = %d
", a[ia], b[ib], target);
54             } else {
55                 printf("Not found.
");
56             }
57         }
58     }
59     
60     return 0;
61 }