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

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

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

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

如果大于目标,end–;

如果小于目标,begin++;

void sum_print(int* arr, int n, int sum)
{
	int i, j;
	for(i=0,j=n-1;i<j && i>=0 && j<n; )
	{
		if(arr[i]+arr[j]==sum)
		{
			printf("%d + %d = %d \n", arr[i], arr[j], sum);
			return ;
		}else if(arr[i]+arr[j]<sum)
		{
			i++;
		}else
		{
			j--;
		}
	}
}

拓展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.