algorithm - O(n² log(n)) 算法找到数组中的所有数字，使得 x² + y² = z² + u²

Question

给定一个正整数数组，找到一个 O(n² log(n)) 算法来找到数字 x, y, z, u 的所有不同数字组合使得它满足

x² + y² = z² + u²

基本上，我看到了如何使用 得到 x2 + y2 = z2 O(n² log(n)) 时间

sort then iterate and use a binary search

但要对额外的 u²

做同样的事情

Answer 1

没有 O(n²logn) 的解决方案，原因很简单，可能有 O(n⁴) 种可能的解决方案，如果您需要找到它们，输出大小本身就是 O(n⁴)。

看看[1,1,1,1,....,1] (a,b),(c,d) 的每个组合都将满足要求。有 Choose(n,4)这是 O(n⁴) 可能的解决方案。

但是，如果我们将输出大小表示为 m , 它可以在 O(n²logn+m) 中完成:

map<number,list<pair>> m = new map
for each i in 1...n:
   for each j in i+1...n:
     map.add(arr[i]^2+arr[j]^2,(i,j))
for each entry number that is key in the map:
   list = map.get(number)
   print all pairs (i,j),(x,y) in the list such that i!=x,j!=u,i!=y,j!=x

在哪里map是一些基于树的 map 。

如果您不想像 [1,1,1...,1] 示例中的“重复答案”(实际上代表列表中的重复元素)，通过更改 map<number,list<pair>>至 map<number,set<pair>> ，并插入值而不是索引 - 你会得到它。