题目
在一个整数序列中找出所有和为 sum 的两个整数的组合打印出来，两个整数排序不同的只算作一组
解答
这个题目很简单，大多数人不假思索就能写出下面的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
/* 时间复杂度 O(n^2) */
void fun1(int a[], int len, int sum) {
for (int i = 0; i < len; i++) {
for (int j = i; j < len; j++) {
if (a[i] + a[j] == sum)
std::cout << a[i] << ", " << a[j] << std::endl;
}
}
}
int main(){
int a[] = {1,2,4,6,7,8,9};
fun2(a, 7, 10);
return 0;
}
但是，我们稍加分析就能得知，这种算法的时间复杂度为O(n^2)，因为它通过两层循环将序列中的整数进行两两对比。
思考还有更好的解决方法吗？有的。
如果我们取出序列中的一个整数 num，那么我们希望能够在序列中找到的另一个值为 sum - num 的数，所以我们可以使用一个 hash 表来存储 sum - num 和 num 组成的键值对。我们知道 hash 表的时间复杂度的常数级的，所以当我们拿到一个整数时，能够很快地通过查 hash 表知道有没有另一个数能与之组成 sum。
我们可以借助 STL 中的 unordered_set 和 unordered_map 来完成，它们的底层都是通过 hash 表实现的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <unordered_map>
/* 时间复杂度 O(n) */
void fun2(int a[], int len, int sum) {
std::unordered_map<int, int> map;
std::unordered_map<int, int>::const_iterator got;
for (int i = 0; i < len; i++)
{
got = map.find(a[i]);
if (got == map.end()) /* 没找到 */
map.insert({sum-a[i], a[i]});
else
std::cout << got->second << ", " << got->first << std::endl;
}
}
int main(){
int a[] = {1,2,4,6,7,8,9};
fun2(a, 7, 10);
return 0;
}
赞赏支持
微信赞赏
支付宝
