基本算法连载（4）－Google的一道面试题

• 题目： 在一个集合S中寻找最大的C，使A+B=C，且A,B,C均在集合当中，时间空间复杂度最低。

• 解题思路：

• 方案一：
  1. 对集合进行快速排序，时间复杂度为O(nlgn)，空间复杂度为O(lgn)；
  2. 从最后一个元素开始，依次调用“在一个有序集合中寻找两个数的和等于给定值的算法”。一次调用需要O(n)，n个元素需要O(n^2)。
  3. 总体来看，此方案的时间复杂度为O(n^2)，空间复杂度为O(lgn)。

• 方案二：
1. 对集合进行快速排序，时间复杂度为O(nlgn)，空间复杂度为O(lgn)；
2. 用排序后的n个数（a[0],a[1],a[2],...a[n-1]）构造n×n的两两和矩阵，此时有m[i][j]=a[i]+a[j]，m[i] [j]<=m[i][j+1],m[i][j]<=m[i+1][j]，在此矩阵中搜索一个数是否存在，时间复杂度为O(n+n)，所以n个数的时间复杂度为O(n^2)。矩阵元素可以直接通过a[i]与a[j]相加动态获得，所以不需要额外开辟空间。
3. 总体来说，此方案的时间复杂度为O(n^2)，空间复杂度为O(lgn)。
4. 具体搜索方法为：对于一个给定的数a，沿着对角线走下去，遇到第一个大于a的数，然后往上走，如果找到就OK，否则不存在。