寻找所有满足 x² + y² = z² + u² 的数组中的数字的 O(n² log(n)) 算法

Question

给定正整数数组，找到一个 O(n² log(n)) 的算法，以查找所有不同的数字组合，包括数字 x、y、z、u，使其满足以下条件：

x² + y² = z² + u²

基本上，我知道如何使用 O(n² log(n)) 时间获得 x² + y² = z²

排序后迭代并使用二进制搜索

但现在需要添加另一个 u²。

- user3552943

---

你尝试过什么？将这些信息添加到问题中总是最好的做法。 - AstroCB

我尝试了一种类似的方法，我们迭代所有可能的x和y（假设已排序），所以它是n^2 - 然后我们需要一个类似的z^2和二进制搜索，但这是O(n^3 log(n))。我有另一个想法-添加所有可能的x^2+y^2和z^2+u^2组合-然后根据两个可能总和数组二进制搜索正确的值-是否可行？需要更多的空间。 - user3552943

你能把那个信息添加到问题中吗？你可能想查看这些提示以获取提问的好方法。谢谢！ - AstroCB

@AdiInbar 算法问题是[so]的主题，但对于[math.se]来说则不太合适。 - Bernhard Barker

将所有数平方并使用此解决方案 - 4-SUM的二次算法（可能是重复的） - Bernhard Barker

可能是四数之和的二次算法的重复问题。 - phuclv

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 是一些基于树的映射。

如果您不想要“重复答案”（实际上指列表中的重复元素），例如 [1,1,1...,1] 的例子，可以通过将 map<number,list<pair>> 更改为 map<number,set<pair>>，并插入值而不是索引 - 就可以解决问题了。

- amit

---

不错的解决方案，如果您使用哈希映射，并且 hash(Pair) = sum(Pair)，则该解决方案应在相同的哈希码上。 - Khaled.K

@KhaledAKhunaifer OP 要求 O(n^2logn)，我假设他正在寻找最坏情况下的行为，使用哈希映射无法保证，这就是为什么我指定它是基于树的。 - amit

Answer 2

输入: 列表 L = { L1, L2, .. Ln }

算法

1. D = { Di | Di = Li^2 } 对所有数字进行平方操作

2. T = { Ti | Ti = Di+Dj, i!=j } 找出不同的2-Sums

3. S = { Si | Si = (Ti,Tj), i!=j, Ti=Tj } 找出相等的2-Sums

分析

T(Step(1)) ~ n

T(Step(2)) ~ (n^2 - n)

T(Step(3)) ~ (n^2 - n)

T = n + (n^2 - n) + (n^2 - n)

T = n^2 + n^2 + n - n - n

T = 2n^2 - n ~ O(n^2)

代码

Solution.Java

class Solution
{
    public static void main (String [] args)
    {
        int [] L = { 1, 2, 3, 4, 5, 6, 2, 4, 6, 3, 3 };

        int [] D = new int [L.length];

        for (int i=0; i<L.length; i++)
            D[i] = (L[i]^2);

        int nbSums = D.length^2 - D.length;
        int z = 0;

        int [] T = new int [nbSums];

        for (int i=0; i<D.length; i++)
            for (int j=0; j<D.length; j++)
                if (i != j)
                    T[z++] = D[i] + D[j];

        ArrayList<Pair> S = new ArrayList<Pair>();

        for (int i=0; i<T.length; i++)
            for (int j=0; j<T.length; j++)
                if (i != j && T[i] == T[j])
                    S.add(new Pair(T[i], T[j]));
    }
}

Pair.java

class Pair
{
    public int a;
    public int b;

    public Pair (int a, int b)
    {
        this.first = a;
        this.second = b;
    }
}

- Khaled.K

---

解决方案存在两个问题。(1) 它不是O(n^2)，如果你需要查找所有元素，就没有O(n^2)的解决方案。(2) 对于列表[1,1,3]，这个解决方案将返回(1,3),(1,3)作为一个解决方案(它重复使用了元素)。 - amit