H-Sum 3s

H-Sum 3s

时间： 1ms        内存：128M

描述：

You are given a number sequence a₁,a₂,a₃...,a_n , your task is to find if there is a pair of interger (i,j) that a_i+a_(i+1)+..+a_j 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 |a_i|<=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;
}

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