我知道此类问题已经发布过,但我想讨论一些新的事情.所以,我发布了它.
给定未排序的整数数组,找到满足x ^ 2 + y ^ 2 = z ^ 2的所有三元组.
例如,如果给定的数组是 - 1,3,7,5,4,12,13答案应该是 - 5,12,13和3,4,5
我建议下面的算法复杂度为O(n ^ 2) -
现在它减少了在排序数组中找到所有三元组(a,b,c)的问题,使得a = b + c.
面试官坚持要求比O(n ^ 2)更好的解决方案.
我已经阅读了维基百科上的3SUM问题,强调问题可以在O(n + ulogu)中解决,如果数字在[-u,u]范围内,假设数组可以表示为位向量.但我无法清楚地了解进一步的解释.
有人可以通过一个很好的例子来帮助我理解发生了什么吗？
首先.在最坏的情况下找到所有三胞胎是O(n^3).假设你有n=3k数字.它们的K是3,k是4,k是5.
3,....,3,4,....,4,5,.....5
有k^3 = n^3/27 = O(n^3)这样的三胞胎.打印它们需要O(n^3)时间.
接下来将以这种形式解释3SUM问题:
s_1, ..., s_n每个都有数字在范围内[-u;u].有多少三胞胎a,b,c有一些a+b=c？
转换.获得2*u数字a_-u, ..., a_0, a_1, ... a_u.a_i是数量s_j,那s_j = i.这是完成的O(n+u)
res = a_0 * sum(i=-u..u, i=/=0, C(a_i, 2)) + C(a_0,3) a_0 = 0
构建一个多项式P(x) = sum(i = -u...u, a_i*x^(i+u).
Q(x) = P(x)*P(x)使用FFT查找.
需要注意的是Q(x) = sum(i=-2u..2u, b_i*x^(i+2*u)),在这里b_i是对数s_u,s_k即s_u+s_k = i(这包括使用相同数目的两倍).
对于所有甚至i做b_i = b_i - a_(i/2).这将使用相同的数字删除两次.
b_i*a_i/2- 将此添加到res.示例:为了更简单,我将假设数字的范围是[0..u]并且不会在x的幂中使用任何+ u.假设我们有数字1,2,3
-a_0 = 0, a_1 = 1, a_2 = 1, a_3 = 1
res = 0
P(x) = x + x^2 + x^3
Q(x) = x^2 +2x^3+3x^4+2x^5+x^6
减去之后 b_2 = 0, b_3 = 2, b_4 = 2, b_5 = 2, b_6 = 0
res += 0*1/2 + 2*1/2 + 2*0/2 + 2*0/2 + 6*0/2 = 1
另一种可能性(谁可以理解采访者的思想？)将重写方程式:
x^2 + y^2 = z^2
x^2 = z^2 - y^2 = (z-y)(z+y)
如果我们知道x ^ 2的素因子化,那么我们可以简单地将所有可能的因子分解为一对数p,q(p <q)并计算
x^2 = p.q = (z-y)(z+y)
p+q = (z-y)+(z+y) = 2z
q-p = (z+y)-(z-y) = 2y
z = (p+q)/2
y = (q-p)/2
因此,给定因子分解x ^ 2 = pq,我们可以计算出z和y值.通过将所有整数值放入一个集合中,我们可以通过查看那些z,y值是否在数组中来检查每个可能的答案时间O(1)(每次检查)(注意也检测到负值) .
维基百科说随机选择的整数具有大约log(n)个除数,所以这应该采用n.log(n)假设你能够足够快地进行因式分解(例如,如果你知道所有整数都在一百万以下就可以预先计算一个数组每个整数的最小因子).