算法复杂度： O(n*∑a[i])

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005],c[100005];
int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
    cin>>a[i];
    int cnt=0;
    for(int i=1; i<=n; i++)
    {
        if(!c[a[i]]) b[a[i]]=1;
        for(int j=1; j<=100000; j++)
        {
            int x,y;
            if(c[j])
            {
                x=abs(a[i]-j),y=a[i]+j;
                if(!c[x]) b[x]=1;
                if(!c[y]) b[y]=1;
            }
        }
        for(int j=1; j<=100000; j++)
        if(b[j]) c[j]=b[j];
    }
    for(int i=1; i<=100000; i++)
    if(c[i])cnt++;
    cout<<cnt;
    return 0;
}