给定一个整数数组,判断其中是否有3个数和为N

C++ 解法, 执行用时: 3ms, 内存消耗: 476KB, 提交时间: 2020-09-15

#include<bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> input;
    int flag=0,m,N;
    while(scanf("%d",&m)!=EOF)
    {
        char e=getchar();
        if(flag==1)
        {
            N=m;
            break;
        }
        else
        {
            input.push_back(m);
            if(e==',')
            {
                flag=1;
            }
        }
    }
    int len=input.size();
    sort(input.begin(),input.end());
    if(len<3||input[0]+input[1]+input[2]>N||(input[len-1]+input[len-2]+input[len-3]<N))
    {
        cout<<"False"<<endl;
        return 0;
    }
    for(int i=0;i<len-2;i++)
    {
        if(input[i]>N/3)
            break;
        int first=i+1,second=len-1,sum;
        while(first<second)
        {
            sum=input[i]+input[first]+input[second];
            if(sum==N)
            {
                cout<<"True"<<endl;
                return 0;
            }
            else if(sum<N)
            {
                first++;
            }
            else
            {
                second--;
            }
        }
    }
    cout<<"False"<<endl;
    return 0;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 496KB, 提交时间: 2020-04-27

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    vector<int>v;
    int t,flag=0,N;
    while(scanf("%d",&t) != EOF)
    {
        char c=getchar();
        if(flag==1)
        {
            N=t;
            break;
        }
        else
        {
            v.push_back(t);
            if(c==',')
                flag=1;
        }
    }
    int n=v.size();
    sort(v.begin(),v.end());
    if(n<3 || (v[0]+v[1]+v[2]>N)||(v[n-1]+v[n-2]+v[n-3]<N))
    {
        cout<<"False"<<endl;
        return 0;
    }
    for(int i=0;i<n-2;++i)
    {
        if(v[i]>N/3)
            break;
        int j=i+1,k=n-1,sum;
        while(j<k)
        {
            sum=v[i]+v[j]+v[k];
            if(sum==N)
            {
                cout<<"True"<<endl;
                return 0;
            }
            else if(sum<N)
                j++;
            else
                k--;
        }
    }
    cout<<"False"<<endl;
    return 0;
}

C 解法, 执行用时: 4ms, 内存消耗: 376KB, 提交时间: 2020-04-28

#include<stdio.h>
 
void quicksort(int a[],int n)
{
    int i=0,j=n-1,m=a[0];
    while(i<j)
    {
        while(i<j&&a[j]>m) {j--;}
        if(i<j)
        {
            a[i]=a[j];
            i++;
        }
        while(i<j&&a[i]<m) {i++;}
        if(i<j)
        {
            a[j]=a[i];
            j--;
        }
    }
    a[i]=m;
    if(i>1) {quicksort(a,i);}
    if(n-i-1>1) {quicksort(a+i+1,n-i-1);}
}
 
int main()
{
    int a[2000];
    int i=0;
    char c;
    for(;i<2000;i++)
    {
        scanf("%d%c",&a[i],&c);
        if(c!=' ') {break;}
    }
    i++;
    scanf("%d%c",&a[i],&c);
    if(c!='\n')
    {
        printf("Error\n");
        return 0;
    }
 
    quicksort(a,i);
 
    int ad,di,j=0;
    int *left,*right;
    _Bool eq=0;
    for(;j<i-2;j++)
    {
        left=&a[j+1];
        right=&a[i-1];
        di=a[i]-a[j];
        while(left<right)
        {
            ad=(*left)+(*right);
            eq=ad==di;
            if(eq) {break;}
            if(ad>di) {right--;}
            else {left++;}
        }
        if(eq) {break;}
    }
    if(eq) {printf("True\n");}
    else {printf("False\n");}
 
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 376KB, 提交时间: 2019-11-20

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    vector<int>v;
    int t,flag=0,N;
    while(scanf("%d",&t) != EOF)
    {
        char c=getchar();
        if(flag==1)
        {
            N=t;
            break;
        }
        else
        {
            v.push_back(t);
            if(c==',')
                flag=1;
        }
    }
    int n=v.size();
    sort(v.begin(),v.end());
    if(n<3 || (v[0]+v[1]+v[2]>N)||(v[n-1]+v[n-2]+v[n-3]<N))
    {
        cout<<"False"<<endl;
        return 0;
    }
    for(int i=0;i<n-2;++i)
    {
        if(v[i]>N/3)
            break;
        int j=i+1,k=n-1,sum;
        while(j<k)
        {
            sum=v[i]+v[j]+v[k];
            if(sum==N)
            {
                cout<<"True"<<endl;
                return 0;
            }
            else if(sum<N)
                j++;
            else
                k--;
        }
    }
    cout<<"False"<<endl;
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 396KB, 提交时间: 2020-10-29

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    vector<int>v;
    int t,flag=0,N;
    while(scanf("%d",&t) != EOF)
    {
        char c=getchar();
        if(flag==1)
        {
            N=t;
            break;
        }
        else
        {
            v.push_back(t);
            if(c==',')
                flag=1;
        }
    }
    int n=v.size();
    sort(v.begin(),v.end());
    if(n<3 || (v[0]+v[1]+v[2]>N)||(v[n-1]+v[n-2]+v[n-3]<N))
    {
        cout<<"False"<<endl;
        return 0;
    }
    for(int i=0;i<n-2;++i)
    {
        if(v[i]>N/3)
            break;
        int j=i+1,k=n-1,sum;
        while(j<k)
        {
            sum=v[i]+v[j]+v[k];
            if(sum==N)
            {
                cout<<"True"<<endl;
                return 0;
            }
            else if(sum<N)
                j++;
            else
                k--;
        }
    }
    cout<<"False"<<endl;
    return 0;
}

详情