H-Sum 3s

H-Sum 3s

时间: 1ms        内存:128M

描述:

You are given a number sequence a1,a2,a3...,an , your task is to find if there is a pair of interger (i,j) that ai+a(i+1)+..+aj equals to 0 and i<=j;

输入:

Input consists of multiple test cases. For each case, the first line of input contains an integer n, the next line follows n integers. (n>=1 && n<=10^5 |ai|<=10^4)

输出:

For each case, if there is at least one pair of integer (i,j) meet the requirement, print “YES”, otherwise print “NO” .

示例输入:

5
1 2 3 4 5
5
3 4 -2 -3 1

示例输出:

NO
YES

提示:

参考答案(内存最优[1752]):

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<ctype.h>
#include<time.h>
int b[100000];
bool fun(int *a,int n)
{
    int i,j;
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    for(i=0;i<n;i++)
        if(!b[i])return true;
    for(i=0;i<n;i++)
    {
        for(j=0;j<i;j++)
        {
            b[j]+=a[i];
            if(!b[j])return true;
        }
    }
    return false;
}
int main()
{
    int n,a[100000];
    while(~scanf("%d",&n))
    printf(fun(a,n)?"YES\n":"NO\n");
    return 0;
}

参考答案(时间最优[152]):

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int a[100005],s[100005];
int main()
{
    long int N,i,k=0;
    while(cin>>N)
    {
        cin>>a[0];
        s[0]=a[0];
        if(a[0]==0){k=1;}
        for(i=1;i<N;i++)
        {
            scanf("%ld",&a[i]);
            s[i]=s[i-1]+a[i];
            if(a[i]==0||s[i]==0)
                k=1;
        }
        if(k==0)
        {
            sort(s,s+N);
            for(i=0;i<N-1;i++)
                if(s[i]==s[i+1])
                {
                    k=1;
                    break;
                }
        }
        if(k==1){cout<<"YES"<<endl;}
        else{cout<<"NO"<<endl;}
        k=0;
    }
    return 0;
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注