在数组中查找两个数之和等于输入的另一个数（栈和队列）

code

6 年前

时间： 1ms 内存：1000M

描述：

题目：输入一个已经按升序排序过的数组和一个数字，
在数组中查找两个数，使得它们的和正好是输入的那个数字。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。

输入：

输入：

1 2 4 7 11 15

15

输出：

输出：

4 11

示例输入：

1 2 4 7 11 15

15

示例输出：

4 11

提示：

参考答案（内存最优[752]）：

#include<stdio.h>  
#include<malloc.h>
#include<string.h>
#define SEN 100  
    
struct sqstack  
{  
    char *base;  
    char *top;  
    int size;  
};  
    
struct sqstack *initEmptyStack()   /*构建空輚*/
{  
    struct sqstack *p;  
    p=(struct sqstack *)malloc(sizeof(struct sqstack));  
    if(p!=NULL)  
    {  
        p->base=(char *)malloc(sizeof(struct sqstack)*SEN);  
        if(p->base!=NULL)  
        {  
            p->top=p->base;  
            p->size=SEN;  
            return p;  
        }  
    }  
    else
        free(p);  
    return NULL;  
}  
    
int push(struct sqstack *p,char a)         /*入栈*/
{  
    *p->top++=a;  
    return 0;  
}  
    
int gettop(struct sqstack *p)             /*取栈顶元素*/
{  
    if(p->base!=p->top)  
        return *(p->top-1);  
    return 0; 
} 
  
int pop(struct sqstack *p)              /*出栈*/
{  
    return *(--p->top);  
}  
    
int main()  
{   
	struct sqstack *p;
	int a[1000];
	int i=0,j,flog=0,t=0,m;
	char c;
	p=initEmptyStack();
	while(scanf("%d",&a[i]))
	{
		scanf("%c",&c);
		if(c=='\n')
			flog=1;
		i++;
		t++;
		if(flog==1)
			break;
	}
	scanf("%d",&m);
	for(i=0;i<t-1;i++)
	{
		push(p,a[i]);
		for(j=i+1;j<t;j++)
			if(gettop(p)+a[j]==m)
				printf("%d %d\n",gettop(p),a[j]);
		pop(p);
	}
    return 0;  
}

参考答案（时间最优[0]）：

#include<stdio.h>  
#include<malloc.h>
#include<string.h>
#define SEN 100  
    
struct sqstack  
{  
    char *base;  
    char *top;  
    int size;  
};  
    
struct sqstack *initEmptyStack()   /*构建空輚*/
{  
    struct sqstack *p;  
    p=(struct sqstack *)malloc(sizeof(struct sqstack));  
    if(p!=NULL)  
    {  
        p->base=(char *)malloc(sizeof(struct sqstack)*SEN);  
        if(p->base!=NULL)  
        {  
            p->top=p->base;  
            p->size=SEN;  
            return p;  
        }  
    }  
    else
        free(p);  
    return NULL;  
}  
    
int push(struct sqstack *p,char a)         /*入栈*/
{  
    *p->top++=a;  
    return 0;  
}  
    
int gettop(struct sqstack *p)             /*取栈顶元素*/
{  
    if(p->base!=p->top)  
        return *(p->top-1);  
    return 0; 
} 
  
int pop(struct sqstack *p)              /*出栈*/
{  
    return *(--p->top);  
}  
    
int main()  
{   
	struct sqstack *p;
	int a[1000];
	int i=0,j,flog=0,t=0,m;
	char c;
	p=initEmptyStack();
	while(scanf("%d",&a[i]))
	{
		scanf("%c",&c);
		if(c=='\n')
			flog=1;
		i++;
		t++;
		if(flog==1)
			break;
	}
	scanf("%d",&m);
	for(i=0;i<t-1;i++)
	{
		push(p,a[i]);
		for(j=i+1;j<t;j++)
			if(gettop(p)+a[j]==m)
				printf("%d %d\n",gettop(p),a[j]);
		pop(p);
	}
    return 0;  
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。