我遇到了一个关于4 4SUM问题的建议解决方案，这个问题应该在O(nlogn)时间内解决。梭罗烯能证明这一点吗？

Question

它的时间复杂度似乎是O(nlogn)，因为我们首先对数组进行排序，然后执行4指针方法(在时间复杂度上是线性的)。

它们使用4个指针LL、LR、RR和RL，其中4个指针的和被加起来，并且根据最优的运动，他们选择相应地移动指针。

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n = 8;
    int a[n] = {1, 2, 3, 4, 6, 5, 7, 8};
    int x = 16;
    sort(a, a + n);
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << ",";
    }
    cout << endl;
    int LL = 0;
    int LR = 1;
    int RL = n - 2;
    int RR = n - 1;
    //cout << LL << "," << LR << "," << RL << "," << RR << endl;
    while (LR < RL)
    {
        if ((a[LL] + a[LR] + a[RL] + a[RR]) > x)
        {
            //cout << (a[LL] + a[LR] + a[RR] + a[RR]) << endl;
            if (a[RL] - a[RL - 1] < ((a[RR] + a[RL]) - (a[RL] + a[RL - 1])))
            {
                RL--;
            }
            else
            {
                RL--;
                RR--;
            }
        }
        else if ((a[LL] + a[LR] + a[RL] + a[RR]) < x)
        {

            if (a[LR + 1] - a[LR] < ((a[LR + 1] + a[LR]) - (a[LL] + a[LR])))
            {
                LR++;
            }
            else
            {
                LL++;
                LR++;
            }
        }
        else
        {
            cout << "The four elements are:" << a[LL] << "," << a[LR] << "," << a[RL] << "," << a[RR];
            return 0;
        }
        //cout << LL << "," << LR << "," << RL << "," << RR << endl;
    }
    cout << "No such four elements exists";
    return 0;
}

Answer 1

我可以把这个(任何一个)解决方案放到4 4SUM中，在多集中添加一个零，并使用它来解决3和问题。

Answer 2

你的逻辑是O(nlogn)，但它不像你想的那样。您的4 4SUM算法主要工作，但这里是一个反例。

首先，让我简化4 4SUM逻辑的"if“和"else if”语句。这里有一个等价物：

if ((a[LL] + a[LR] + a[RL] + a[RR]) > x)
{
    if (a[RL] < a[RR])
    {
        RL--;
    }
    else
    {
        RL--;
        RR--;
    }
}
else if ((a[LL] + a[LR] + a[RL] + a[RR]) < x)
{

    if (  a[LR] >  a[LL])
    {
        LR++;
    }
    else
    {
        LL++;
        LR++;
    }
}
else
{
    cout << "The four elements are:" << a[LL] << "," << a[LR] << "," << a[RL] << "," << a[RR];
    return 0;
}

这里有一个反例：

有序阵列: 1，2，3，5，6，7

目标和: 14

迭代1:

LL = 1，LR = 2，RL =6，RR =7

16 > 14而RL < RR则RL--

迭代2:

LL = 1，LR = 2，RL =5，RR =7

15 > 14和RL < RR然后RL

迭代3:

LL = 1，LR = 2，RL =3，RR =7

13 < 14，LR > LL然后是LR++

迭代4:

LL = 1，LR = 3，RL =3，RR =7

无效，使用相同数字的两倍