求和三元组的算法？

Question

我们有一个包含 m 个正整数的数组 A，什么算法可以

return 如果 A 中有一个三元组 (x,y,z) 则为真这样 A[x] + A[y] + A[z] = 200

否则return错误。数组中的数字是不同的，运行时间必须是 O(n)。

我想出了 O(n^3)。关于如何使用 O(n) 实现此目的的任何想法？

Answer 1

这被称为 3SUM 问题，目前还没有线性解。我提供了一个伪代码运行 O(n^2) 使用二进制搜索算法：

sumTriple(А[1...n]: array of integers,sum: integer): bool

 sort(A)

 for i ← 1 to n-2
  j ← i+1
  k ← n

  while k > j
   if A[i]+A[j]+A[k] = sum
    print i,j,k
    return true

   else if A[i]+A[j]+A[k] > sum
    k ← k-1

   else // A[i]+A[j]+A[k] < sum
    j ← j+1

return false

您可以找到有关该问题的更多信息和更多详细信息 here.

Answer 2

由于元素是唯一的，这归结为在 O(n) 中预处理数组以过滤冗余元素 - 大于 200（其中 none 将在三元组中）。

那么，你有一个大小不超过 200 的数组。

检查这个数组中的所有三元组是O(200^3)=O(1)（不过就常量而言可以更有效地完成）。

所以，这将是 O(n) U O(200^3) = O(n)

Answer 3

我想你可以用位运算来解决这个问题。比如C++ STL中的bitset。

使用3个bitsets，第一个bitset缓存所有可以加1的数，第二个bitset缓存所有可以加2的数，第三个bitset缓存所有可以加1的数添加3个数字。然后如果有新的数字来了，你可以通过简单的位操作来维护位集。

这是一个示例 C++ 代码：

bitset<256> bs[4];
for (int i = 0; i < 4; ++i)
    bs[i].reset();

int N, number;

cin >> N;
while (N--)
{
    cin >> number;

    bs[3] |= (bs[2] << number);
    bs[2] |= (bs[1] << number);
    if (number <= 200)
        bs[1].set(number);

    //cout << "1: " << bs[1] << endl;
    //cout << "2: " << bs[2] << endl;
    //cout << "3: " << bs[3] << endl;
}

cout << bs[3][200] << endl;

算法复杂度为O(n)。因为bit操作很快，每个64位long类型可以缓存64个数，所以如果不想用bitset，可以用4个long类型(64 * 4 = 256)代替。

Answer 4

我同意@amit 的解决方案，但有一个问题：我们怎样才能让它变得更好，在我们的例子中只是更快。

这是我的解决方案，它几乎基于 amit 的想法，但是渐近复杂度 == O(n + sum*(sum+1)/2)，其中 n 是输入数组的长度。

首先，我们需要n步来过滤输入数组并将每个值减去总和放入新数组中，其中值的索引等于该值。在此步骤结束时，我们得到了大小等于 sum 的数组，我们可以访问 O(1).

中的任何值

最后，要找到 x,y,z 我们只需要 sum*(sum+1)/2 步。

typedef struct SumATripleResult
{
    unsigned int x;
    unsigned int y;
    unsigned int z;
} SumATripleResult;

SumATripleResult sumATriple(unsigned int totalSum, unsigned int *inputArray, unsigned int n)
{
    SumATripleResult result;

    unsigned int array[totalSum];

    //Filter the input array and put each value into 'array' where array[value] = value
    for (size_t i = 0; i<n; i++)
    {
        unsigned int value = inputArray[i];

        if(value<totalSum)
        {
            array[value] = value;
        }
    }

    unsigned int x;
    unsigned int y;
    unsigned int z;

    for (size_t i = 0; i<totalSum; i++)
    {
        x = array[i];

        for (size_t j = i+1; x>0 && j<totalSum; j++)
        {
            y = array[j];

            if( y==0 || x + y >= totalSum) continue;

            unsigned int zIdx = totalSum - (x + y);

            if(zIdx == x || zIdx == y) continue;

            z = array[zIdx];

            if( z != 0)
            {
                result.x = x;
                result.y = y;
                result.z = z;
                return result;
            }
        }
    }

    //nothing found
    return result;
}

//Test
unsigned int array[] = {1, 21, 30, 12, 15, 10, 3, 5, 6, 11, 17, 31};

SumATripleResult r = sumATriple(52, array, 12);
printf("result = %d %d %d", r.x, r.y, r.y);

r = sumATriple(49, array, 12);
printf("result = %d %d %d", r.x, r.y, r.y);

r = sumATriple(32, array, 12);
printf("result = %d %d %d", r.x, r.y, r.y);

求和三元组的算法？

Algorithm to sum a triple?

algorithm

big-o

asymptotic-complexity