如何在阵列中找到比O(N ^ 2)更快的毕达哥拉斯三胞胎？

Question

有人可以提出一种算法,在给定数组中的数字中找到所有毕达哥拉斯三元组吗？如果可能,请建议比O(n ²)更快的算法.

勾股数是一组{A,B,C},使得² = B ² + C ².示例:对于数组 [9, 2, 3, 4, 8, 5, 6, 10],算法的输出应为{3, 4, 5}和{6, 8, 10}.

Answer 1

我理解这个问题

给定一个数组,找到所有这样的三元组i,j并且k,这样a [i] ² = a [j] ² + a [k] ²

该解决方案的关键思想是:

• 平方每个元素.(这需要O(n)时间).这将把原始任务减少为"在数组中找到三个数字,其中一个是其他两个数字的总和".

现在你知道如何在不到O(n ²)的时间内解决这样的任务,使用这样的算法.出于我的想法,只有以下O(n ²)解决方案:

1. 按升序对数组进行排序.这需要O(n log n).

2. 现在考虑每个元素a [i].如果a [i] = a [j] + a [k],那么,由于数字是正的并且数组现在被排序,因此k <i且j <i.

   为了找到这样的指标,运行一个循环,增加j从1到i,并减少k来自i于0在同一时间,直到他们满足.增加jif a[j]+a[k] < a[i],k如果总和大于,则减少a[i].如果总和相等,那就是答案之一,打印它并移动两个索引.

   这需要O(i)操作.

3. 对每个索引重复步骤2 i.这样你就需要完全O(n ²)次操作,这将是最终的估计.

Answer 2

对于密切相关的3SUM问题(http://en.wikipedia.org/wiki/3SUM),没有人知道如何做得比二次方显着更好.我认为快速解决问题的可能性不太可能.

3SUM问题是找到a + b + c = 0.当输入是实数代数数时,让PYTHTRIP成为找到^ 2 + b ^ 2 = c ^ 2的问题.这是从3SUM到PYTHTRIP的O(n log n)时间减少.正如ShreevatsaR指出的那样,这并不排除数论理论的可能性(或3SUM的解决方案!).

首先我们将3SUM减少到一个我称之为3SUM-ALT的问题.在3SUM-ALT中,我们想要找到一个+ b = c,其中所有数组条目都是非负的.从3SUM-ALT到PYTHTRIP的完成减少只是取得了根源.

为了使用3SUM-ALT求解3SUM,首先消除a,b,c之一为零(O(n log n))的三元组的可能性.现在,任何满意的三元组都有两个正数和一个负数,或者两个负数和一个正数.设w是大于任何输入数的绝对值的三倍的数.求解3SUM-ALT的两个实例:其中所有负x映射到w-x,所有正x映射到2w + x; 一个所有负x映射到2w-x而所有正x映射到w + x.其余的证据很简单.

Answer 3

我还有一个解决方案,

//sort the array in ascending order 
//find the square of each element in the array

//let 'a' be the array containing square of each element in ascending order 

for(i->0 to (a.length-1))
  for (j->i+1 to  (a.length-1))
    //search the a[i]+a[j] ahead in the array from j+1 to the end of array
      //if found get the triplet according to sqrt(a[i]),sqrt(a[j]) & sqrt(a[i]+a[j])
  endfor
endfor

Answer 4

如果 (a, b, c) 是毕达哥拉斯三元组，则任何正整数的 (ka, kb, kc) 也是毕达哥拉斯三元组。

因此，只需为 a、b 和 c 找到一个值，然后您就可以计算出任意数量的新值。

伪代码：

a = 3
b = 4
c = 5
for k in 1..N:
  P[k] = (ka, kb, kc)

如果这不正是您想要的，请告诉我。