在数组中求和的快速算法

Question

我正在寻找一个快速的算法:

我有一个大小为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))

请分享您对此问题的想法,谢谢

Answer 1

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

这基本上就是3SUM问题.没有潜在的无限大的元素,最着名的算法是近似的O(n^2),但我们只证明它不能比O(n lg n)大多数计算模型更快.

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

我知道如何与FFT解决的问题是找到在阵列的长度为3的算术序列:即,一个序列a,b,c与c - b = b - a,或等价地,a + c = 2b.

不幸的是,转型的最后一步并不像我想的那么快,但是当我们到达那里时,我会谈到这一点.

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

1. 找出最小u和最大v的X的O(n)时间.我们u'是min(u, u*2)和v'是max(v, v*2).

2. 构造一个Z长度为二进制数组(bitstring)v' - u' + 1; Z[i]如果其中一个X或两个[x_1*2, ..., x_n*2]包含,则为true u' + i.这是O(n)初始化; 只需遍历每个元素X并设置两个相应的元素Z.

   当我们构建这个数组时,我们可以将我们找到的任何重复项的索引保存到辅助列表中Y.一旦Z完成,我们只是检查2 * x_i每个x_i在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 ² + x ³ + x ⁴ + x ⁵ + x ⁹.

   现在,记住高中代数中两个多项式的乘积中的x ^c的系数是所有a,b的和,其中第一个多项式系数的+ b = c是x ^b的第二个系数的x ^a倍.所以,如果我们考虑Q = p ²,系数X ^2J(为一个Ĵ用)将超过所有的总和我的.但由于是二进制,这正是三元组i,j,k的数量,它们是均匀间隔的.请注意,(j,j,j)总是这样的三元组,所以我们只关心值> 1的那些.Z[j] = 1Z[i] * Z[2*j - i]ZZ

   然后,我们可以使用快速傅立叶变换找到p ²的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,2*x_j对于一些j(通过检查Z[2*(x_k - x_j) - u']).如果是这样,我们有答案; 如果我们通过所有X没有命中,那么FFT只发现虚假的答案,我们必须检查另一个元素W.

   因此,最后一步是O(n*1 +(具有W [2*(x_k-u')]> 1的x_k的数量,其实际上不是解)),这可能是O(n^2),这显然是不可行的.应该有办法避免在输出中产生这些虚假的答案W; 如果我们知道任何合适的W系数肯定有答案,那么最后一步就是O(n)并且一切都会好的.

   我认为可以使用一个稍微不同的多项式来做到这一点,但我还没有实际工作.我会考虑一下......

部分基于这个答案.