6

我正在寻找一种快速算法：

我有一个大小为 n 的 int 数组，目标是找到数组中的所有模式
x1, x2, x3 are different elements in the array, such that x1+x2 = x3

例如，我知道有一个大小为 3 的 int 数组，[1, 2, 3]那么只有一种可能性：1+2 = 3（考虑 1+2 = 2+1）

我正在考虑实现 Pairs 和 Hashmaps 以使算法更快。（我现在最快的还是O(n^2))

请分享您对这个问题的想法，谢谢

4

3 回答 3

10

编辑：下面的答案适用于这个问题的一个版本，在这个版本中你只想要一个像这样加起来的三元组。当你想要所有这些时，因为可能至少有 O(n^2) 可能的输出（如 ex0du5 所指出的那样），甚至在重复元素的病理情况下甚至 O(n^3)，你不会击败基于散列的简单 O(n^2) 算法（从一个值映射到具有该值的索引列表）。

这基本上是 3SUM 问题。如果没有可能无限大的元素，最著名的算法是近似O(n^2)，但我们只是证明它不能比O(n lg n)大多数计算模型更快。

如果整数元素位于范围内，您可以使用FFT[u, v]进行稍微不同的版本。我将描述一个将这个问题转化为那个问题的过程，在那里解决它，然后根据这个转换找出你的问题的答案。O(n + (v-u) lg (v-u))

我知道如何用 FFT 解决的问题是在一个数组中找到一个长度为 3 的算术序列：即一个序列a, b, cwithc - b = b - a或等价的a + c = 2b.

不幸的是，转换回来的最后一步并没有我想要的那么快，但是当我们到达那里时我会谈到这一点。

让我们调用您的原始数组X，其中包含整数x_1, ..., x_n。我们想找到索引i, j,k这样x_i + x_j = x_k。

  1. 找出时间的最小值u和最大值v。让我们成为。_XO(n)u'min(u, u*2)v'max(v, v*2)

  2. Z构造一个长度为 的二进制数组（位串）v' - u' + 1；Z[i]如果其中一个X或它的双精度[x_1*2, ..., x_n*2]包含，则为真u' + i。这是O(n)初始化；只需遍历 的每个元素X并设置 的两个对应元素Z。

    在构建这个数组时，我们可以将找到的任何重复项的索引保存到辅助列表中Y。完成后，Z我们只需检查2 * x_i每个x_iin 。Y如果有的话，我们就完成了；否则重复是无关紧要的，我们可以忘记Y. （唯一稍微复杂一点的情况是如果0重复；那么我们需要三个不同的副本来获得解决方案。）

    现在，您的问题的一个解决方案，即x_i + x_j = x_k，将出现在Z三个均匀分布的解决方案中，因为一些简单的代数运算给了我们2*x_j - x_k = x_k - 2*x_i。请注意，末尾的元素是我们特殊的双重条目（from 2X），中间的元素是常规条目（from X）。

  3. 考虑Z作为多项式的表示p，其中度项的系数i是Z[i]。如果X是[1, 2, 3, 5]，那么Z是1111110001（因为我们有 1、2、3、4、5、6 和 10）；p然后是1 + x + x 2 + x 3 + x 4 + x 5 + x 9。

    现在，从高中代数中记住，x c在两个多项式的乘积中的系数是所有a, b与a + b = c的第一个多项式的系数x a乘以第二个多项式的系数x b的总和。因此，如果我们考虑q = p 2 ，则x 2j的系数（对于带有 的j ）Z[j] = 1将是所有i的总和Z[i] * Z[2*j - i]。但由于Z是二元的，这正是三元组i,j,k的数量，它们是Z. 注意(j, j, j)总是这样的三元组，所以我们只关心值 > 1 的。

    然后我们可以使用快速傅里叶变换及时找到p 2，O(|Z| log |Z|)其中|Z|是v' - u' + 1。我们得到另一个系数数组；叫它W。

  4. 循环遍历x_k. X（回想一下，我们想要的等间距的都以 的元素为中心X，而不是2*X。）如果W这个元素的两倍，即W[2*(x_k - u')]，对应的是 1，我们知道它不是任何非平凡级数的中心，我们可以跳过它。（如前所述，它应该只是一个正整数。）

    否则，它可能是我们想要的进展的中心（所以我们需要找到i和j）。但是，不幸的是，它也可能是没有我们想要的形式的进展的中心。所以我们需要检查。循环 , 的其他元素x_i，并检查是否有X一个带有2*x_i,x_k的三元组（通过检查）。如果是这样，我们有一个答案；如果我们顺利通过所有这些，那么 FFT 只会找到虚假的答案，我们必须检查.2*x_jjZ[2*(x_k - x_j) - u']XW

    因此，最后一步是 O(n * 1 + (x_k 与 W[2*(x_k - u')] > 1 实际上不是解决方案的数量))，这可能是O(n^2)，这显然是不行的。应该有一种方法可以避免在输出中生成这些虚假答案W；如果我们知道任何适当W的系数肯定有答案，那么最后一步就可以O(n)了，一切都会好起来的。

    我认为可以使用稍微不同的多项式来做到这一点，但我还没有让它真正起作用。我再考虑考虑一下......

部分基于这个答案。

于 2012-04-24T18:51:17.623 回答
1

它必须至少为 O(n^2)，因为有 n(n-1)/2 个不同的总和可以检查其他成员。您必须计算所有这些，因为任何求和的对都可能是任何其他成员（从一个示例开始并排列所有元素以说服自己必须检查所有元素）。或者看看斐波那契的具体内容。

因此，计算它并在哈希表中查找成员给出了摊销 O(n^2)。如果您需要最好的最坏情况，或者使用有序树。

于 2012-04-24T18:49:40.293 回答
1

您基本上需要找到所有不同的值对总和，所以我认为您不会比 O(n 2 ) 做得更好。但是您可以通过对列表进行排序并减少重复值来优化，然后只将一个值与任何等于或更大的值配对，并在总和超过列表中的最大值时停止。

于 2012-04-24T18:54:32.863 回答