已知有序数列A[1..n]和一个正整数x，设计一个复杂度为O(n)的算法，判断A中是否有两个元素它们的和是x。数列中若是整数我会做，但若是分数该如何求解呢？我的整数解法是用空间换时间，

Question

已知有序数列A[1..n]和一个正整数x，设计一个复杂度为O(n)的算法，判断A中是否有两个元素它们的和是x。
数列中若是整数我会做，但若是分数该如何求解呢？
我的整数解法是用空间换时间，就是用x减去所有大于x/2的数，得出结果放在一个大小为[x/2]的数组a中，其值与数组中的位置对应，若有此值，则数组相应位置设为1，然后遍历小于x/2的数，对数m，若数组中对应位置a[m]为1，则返回true，若没有一个对应位置为1，则为false...

Answer 1

你的算法不够好，如果整数很大(比如都是10亿以上),你哪有那么大的内存去开数组呢?
有一个算法是:
建立两个指针p,q,p指向数组第一个元素，q指向数组最后一个元素,[p]表示p内容，算法可以写成:
while(p x)
break;
}
q--;
}
return false;
数组每个元素最多只被p,q一个指针扫描一次，所以总时间复杂度O(N),而且数组元素可以为任意类型