我正在寻找一种快速算法：
我有一个大小为 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）
我正在考虑实现对和哈希图以使算法更快。 （我现在最快的还是O(n^2))
请分享您对这个问题的想法，谢谢
Edit：下面的答案适用于这个问题的一个版本，其中您只想要一个像这样加起来的三元组。当您想要所有这些时，由于可能至少有 O(n^2) 种可能的输出（如 ex0du5 所指出的），甚至在重复元素的病理情况下甚至是 O(n^3) 种，因此您不会击败基于散列的简单 O(n^2) 算法（从一个值映射到具有该值的索引列表）。
这基本上是3SUM问题 http://en.wikipedia.org/wiki/3SUM。如果没有潜在的无限大元素，最著名的算法大约是O(n^2)，但我们只是证明了它不能比O(n lg n)对于大多数计算模型。
如果整数元素位于范围内[u, v]，你可以做一个稍微不同的版本O(n + (v-u) lg (v-u))与FFT http://en.wikipedia.org/wiki/Fast_Fourier_transform。我将描述一个过程，将这个问题转化为那个问题，在那里解决它，然后根据这个转化找出问题的答案。
我知道如何用FFT解决的问题是在数组中找到长度为3的算术序列：即一个序列a, b, c with c - b = b - a，或等价地，a + c = 2b.
不幸的是，转变的最后一步并没有我想要的那么快，但当我们到达那里时我会谈论这个。
让我们调用你的原始数组X，其中包含整数x_1, ..., x_n。我们想要找到索引i, j, k这样x_i + x_j = x_k.
找到最小值u和最大v of X in O(n)时间。让u' be min(u, u*2) and v' be max(v, v*2).
-
构造一个二进制数组（位串）Z长度v' - u' + 1; Z[i]为真，如果X或其双倍[x_1*2, ..., x_n*2]包含u' + i。这是O(n)初始化；只需遍历每个元素X并设置两个相应的元素Z.
当我们构建这个数组时，我们可以将找到的任何重复项的索引保存到辅助列表中Y. Once Z已完成，我们只需检查2 * x_i对于每个x_i in Y。如果有的话，我们就完成了；否则重复项是无关紧要的，我们可以忘记Y。 （唯一稍微复杂的情况是如果0被重复；那么我们需要它的三个不同的副本才能得到解决方案。）
现在，解决您的问题，即x_i + x_j = x_k，将出现在Z作为三个均匀分布的，因为一些简单的代数运算给我们2*x_j - x_k = x_k - 2*x_i。请注意，末尾的元素是我们特殊的双条目（来自2X），中间的一个是常规条目（来自X).
-
Consider Z as a representation of a polynomial p, where the coefficient for the term of degree i is Z[i]. If X is [1, 2, 3, 5], then Z is 1111110001 (because we have 1, 2, 3, 4, 5, 6, and 10); p is then 1 + x + x2 + x3 + x4 + x5 + x9.
Now, remember from high school algebra that the coefficient of xc in the product of two polynomials is the sum over all a, b with a + b = c of the first polynomial's coefficient for xa times the second's coefficient for xb. So, if we consider q = p2, the coefficient of x2j (for a j with Z[j] = 1) will be the sum over all i of Z[i] * Z[2*j - i]. But since Z is binary, that's exactly the number of triplets i,j,k which are evenly-spaced ones in Z. Note that (j, j, j) is always such a triplet, so we only care about ones with values > 1.
We can then use a Fast Fourier Transform http://en.wikipedia.org/wiki/Fast_Fourier_transform to find p2 in O(|Z| log |Z|) time, where |Z| is v' - u' + 1. We get out another array of coefficients; call it W.
-
循环每个x_k in X。 （回想一下，我们想要的均匀分布的都集中在一个元素上X, not 2*X.)如果对应W对于该元素的两倍，即W[2*(x_k - u')], 是 1，我们知道它不是任何重要级数的中心，我们可以跳过它。 （如前所述，它只能是正整数。）
否则，它可能是我们想要的进展的中心（所以我们需要找到i and j）。但不幸的是，它也可能是一个没有我们想要的形式的进展的中心。所以我们需要检查一下。循环其他元素x_i of X，并检查是否存在三元组2*x_i, x_k, 2*x_j对于一些j（通过检查Z[2*(x_k - x_j) - u']）。如果是这样，我们就有了答案；如果我们能完成所有的X如果没有命中，那么 FFT 只发现虚假答案，我们必须检查另一个元素W.
因此，最后一步是 O(n * 1 + (x_k 的数量，其中 W[2*(x_k - u')] > 1 实际上不是解决方案))，这可能是O(n^2)，这显然是不行的。应该有一种方法可以避免在输出中生成这些虚假答案W;如果我们知道任何适当的W系数肯定有答案，最后一步是O(n)一切都会好起来的。
我认为可以使用稍微不同的多项式来做到这一点，但我还没有让它真正发挥作用。我再考虑一下......
部分基于这个答案 https://stackoverflow.com/a/1585303/344821.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
