温故知新,基础复习(一个有序从大到小不重复的数列,任意给出一个sum值,求出数列中所有满足和为sum的数对)

  1. 云栖社区>
  2. 博客>
  3. 正文

温故知新,基础复习(一个有序从大到小不重复的数列,任意给出一个sum值,求出数列中所有满足和为sum的数对)

宋金时 2015-07-21 22:15:03 浏览533
展开阅读全文

温故知新,基础复习(一个有序从大到小不重复的数列,任意给出一个sum值,求出数列中所有满足和为sum的数对)


#include<stdio.h>
#include<stdlib.h>
void PrintSumNumbers(int Arra[],int ASize,int Sum)
{
	//O(1)
	if (ASize<2)
	{
		printf("The size of the Arra is invalid.\n");
		return;
	}
    if(Sum>=0) {
        if(Arra[ASize-1]>=Sum || Arra[0]<=0) {
        	printf("The minimum value is bigger than the sum or the maximum value is equal or lesser than 0. \n");
        	return;
        }
    }

    if (Sum<0)
    {
    	if (Arra[0]<=Sum || Arra[ASize-1]>=0) {
    		printf("The maximum value is smaller than the sum or the minimum value is equal or greater than 0. \n");
    		return;
    	}
    }

	int LeftIndex=0,RightIndex=ASize-1;
    int MinTempValue = Arra[ASize-1];
    int MaxTempValue = Arra[0];
    if (Sum>=0&&MinTempValue<0)
    {
    	if (MaxTempValue>=0)
    	{
    		MinTempValue = Sum-MaxTempValue;
    		for (int i = ASize-1; i != 0; i--)
    		{
    			if (Arra[i]>=MinTempValue)
    			{
    				RightIndex=i;
    				break;
    			}
    		}
    	}
    }
    else {
    	MaxTempValue = Sum-Arra[ASize-1];
	    for(int i=0;i<RightIndex;i++) {
	    	if(Arra[i]<=MaxTempValue) {
	    		LeftIndex=i;
	    		break;
	    	}
	    }
    }
	

    while( LeftIndex<RightIndex)
    {
    	int TempValue = Arra[LeftIndex]+Arra[RightIndex];
    	if(TempValue==Sum) {
    		printf("(%d) + (%d) = (%d)\n",Arra[LeftIndex],Arra[RightIndex],Sum );
    		LeftIndex++;
    		RightIndex--;
    	}
    	else if (TempValue>Sum)
    	{
    		LeftIndex++;
    	}
    	else {
    		RightIndex--;
    	}
    }
}

int main()
{
    int Arra[] = {2147483647,2147483646,9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-2147483646,-2147483647,-2147483647-1};
    PrintSumNumbers(Arra,sizeof(Arra)/sizeof(Arra[0]),2147483647);
}



网友评论

登录后评论
0/500
评论
宋金时
+ 关注