一个例子：


根据这个问题很容易想到用一个四重循环来写，通过暴力求解得方法，代码如下：

#include<bits/stdc++.h>
using namespace std;

const int MAX_N = 50;

int main()
{
    int n,m,k[MAX_N];

    bool f = false;//判断是否能找到和为m得四个数字
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        scanf("%d",k[i]);
    }

    for(int a=0;a<n;a++)
    {
        for(int b=0;b<n;b++)
        {
            for(int c=0;c<n;c++)
            {
                for(int d=0;d<n;d++)
                {
                    if(k[a]+k[b]+k[c]+k[d] == m)
                    {
                        f = true;
                    }
                }
            }
        }
    }
    if(f)
        puts("yes");
    else 
        puts("no");
    return 0;
}

/*
n=3
m=9
k={1,3,5}

no
*/

更快的方法：二分查找

我们发现用四重循环的时间复杂度为O(n4)，我们利用二分查找来代替最里面那一层的循环，在用二分查找之前需要我们排序，而排序的时间复杂度为O(nlogn),二分查找的时间复杂度为O(logn),代替最里层的循环后，总时间复杂度为O(n3logn),所以时间复杂度为O(n^3logn)。

  • 代码如下：
#include<bits/stdc++.h>
using namespace std;

const int MAX_N = 50;
int n,m,k[MAX_N];

bool Binary_Search(int x)
{
    int l=0,r=n;//这里要求r必须等于n，也就是说要多出一个无用的数组位，因为当x=k[n-1]时，l最终会等于n-1，如果r=n-1则会提前退出循环
    while(r-l >= 1)
    {
        int i = (r+l)/2;
        if(k[i] == x) return true;
        else if(k[i] < x) l = i+1;
        else r = i;
    }
    return false;
}

int main()
{
    bool f = false;//判断是否能找到和为m得四个数字

    scanf("%d%d",&n,&m);

    for(int i=0;i<n;i++)
    {
        scanf("%d",&k[i]);
    }
    sort(k,k+n);//将数组排序

    for(int a=0;a<n;a++)
    {
        for(int b=0;b<n;b++)
        {
            for(int c=0;c<n;c++)
            {
                if(Binary_Search(m-k[a]-k[b]-k[c]))
                    f = true;
            }
        }
    }
    if(f)
        puts("yes");
    else 
        puts("no");
    return 0;
}

/*
n=3
m=9
k={1,3,5}

no
*/

再优化：

  • 再使用了二分查找之后时间复杂度为O(n^3logn),可以利用二分查找进一步的优化，我们可以将四重循环的内两层循环换成二分查找，这时候的式子为k[c]+k[d] = m-k[a]-k[b],我们需要一个数组来保存k[c]+k[d]的所有情况。
  • 这时候的时间复杂度：
  • 1.排序时间复杂度：O(n^2logn)
  • 2.循环加二分查找复杂度：O(n^2logn)
  • 到这里我们可以发现，再去一层循环已经没有意义了，因为此时的数组排序时间复杂度为O(n^3logn).
  • 代码如下：
#include<bits/stdc++.h>
using namespace std;

const int MAX_N = 50;
int n,m,k[MAX_N];
int kk[MAX_N*MAX_N];

bool Binary_Search(int x)
{
    int l=0,r=n;//这里要求r必须等于n，也就是说要多出一个无用的数组位，因为但x=k[n-1]时，l最终会等于n-1，如果r=n-1则会提前退出循环
    while(r-l >= 1)
    {
        int i = (r+l)/2;
        if(kk[i] == x) return true;
        else if(kk[i] < x) l = i+1;
        else r = i;
    }
    return false;
}

int main()
{
    bool f = false;//判断是否能找到和为m得四个数字

    scanf("%d%d",&n,&m);

    for(int i=0;i<n;i++)
    {
        scanf("%d",&k[i]);
    }
    for(int c=0;c<n;c++)
    {
        for(int d=0;d<n;d++)
        {
            kk[c*n+d] = k[c] + k[d];
        }
    }

    sort(kk,kk+n*n);//将数组排序

    for(int a=0;a<n;a++)
    {
        for(int b=0;b<n;b++)
        {
            if(Binary_Search(m-k[a]-k[b]))
                    f = true;
        }
    }
    if(f)
        puts("yes");
    else 
        puts("no");
    return 0;
}
/*
n=3
m=9
k={1,3,5}

no
*/