给定一个无序数组和一个常数k，在数组中查找指定条件的两个数，使得两数之和等于k。
简单的方法就不说了，直接上比较理想的方法：
先对数组排序，然后两个游标，一个在数组头，一个在数组尾，然后两头遍历。
代码如下：
1 int cmp(const void *a, const void *b) {
2 return *(int *)a - *(int *)b;
3 }
4
5 struct result {
6 int first;
7 int second;
8 };
9
10 result find_two_numbers(int *a, int n, int k) {
11 int i = 0, j = n - 1;
12 result res = {-1, -1};
13
14 if (a == NULL || n < 2) {
15 return res;
16 }
17
18 qsort(a, n, sizeof(int), cmp);
19
20 while (i < j) {
21 if (a[i] + a[j] == k) {
22 res.first = i;
23 res.second = j;
24 return res;
25 } else if (a[i] + a[j] < k) {
26 i++;
27 } else {
28 j--;
29 }
30 }
31 return res;
32 }
算法复杂度为O(nlogn)。
扩展，如果不是两个数字而是三个数字呢？其实还是可以利用上面的方法做的，只不过得稍微转化一下问题，因为要求的是三个数，而我们可以把三个数的和 a[i] + a[j] + a[r] = k转化为两个数的和a[j] + a[r] = k - a[i]，这样，其实只需要在上层while循环中添加一层for循环，每次变化k的值为k1 = k - a[i]即可，代码如下：
1 struct result_three {
2 int first;
3 int second;
4 int third;
5 };
6
7 result_three find_three_numbers(int *a, int n, int k) {
8 int i, j, r;
9 result_three res = {-1, -1, -1};
10
11 if (a == NULL || n < 3) {
12 return res;
13 }
14
15 qsort(a, n, sizeof(int), cmp);
16
17 for (i = 0; i < n; ++i) {
18 int k1 = k - a[i];
19 j = 0, r = n - 1;
20 while (j < r) {
21 if (j == i) {
22 j++;
23 continue;
24 }
25 if (r == i) {
26 r--;
27 continue;
28 }
29
30 if (a[j] + a[r] == k1) {
31 res.first = i;
32 res.second = j;
33 res.third = r;
34 return res;
35 } else if (a[j] + a[r] < k1) {
36 j++;
37 } else {
38 r--;
39 }
40 }
41 }
42 return res;
43 }
上面算法复杂度很明显为O(nlogn + n
2) = O(n
2)。
现在问题又变了，假如数组中不存在某两个数的和为k，现在要找出某两个数的和最接近k，那么怎么做呢？其实答案非常简单，只需要在两个游标i和j遍历过程中顺便用一个变量delta记录|a[i] + a[j] - t|即可，代码略。
posted on 2012-09-05 22:28
myjfm 阅读(725)
评论(0) 编辑 收藏 引用 所属分类:
算法基础