有序数组,求满足数字之和的两个数

原题是编程之美上的,数组无序。书上面的最优解法是先排序。。。所以有了这道题。

前提是有序,所以可以用O(n)解决。

即begin和end两个下标,往中间凑。如果sum满足输出。

如果大于目标,end–;

如果小于目标,begin++;

拓展1:如果是无序的、但是知道数字的范围怎么办?

可以空间换时间,用计数排序思路,O(n)时间扫描数组,在flag[a[i]]里记录。

然后第二趟O(n),扫描数组,对于每个a[i],查找flag[sum-a[i]]是否为1,如果为1就输出即可。

 

 

Leave a Reply

Your email address will not be published.