我有一组 3d 点。每个点都有一个 x、y 和 z 坐标。数组的最大大小可以是 777777。我有 Q 个查询，每个查询都为我提供四个数字 A、B、C、D。对于每个查询，我必须输出以下总和。
Q <=77
1 <= A, B, C <=77
1 <= Xi, Yi, Zi <=77
1 <= Di <= 777
N <= 777777
我所做的:对于每个查询，使用两个嵌套循环计算给定的总和，复杂度为 O(Q*N^2)。有没有更好的计算方法？
编辑: 我可以肯定的是，这不是几何问题。 xi-xj 的最大值为 76，最小值为 -76。这也适用于 yi 和 zi。所以总共可能的组合是 153*153*153。现在在一个查询中，我们必须计算特定组合在数组中出现的次数，并且只计算该组合的总和一次。问题简化为查找特定组合 (xi-xj, yi-yj, zi-zj) 的次数。有人可以从这里开始吗？我怀疑我们可以在这里使用快速傅里叶变换。我以前见过他们习惯于解决这类问题。但我不知道如何开始
最佳答案
下面是错误的，因为它忽略了绝对值函数。我看不出有什么办法可以克服这个问题。
您可以将查询重写为 A * SUM_i!=j (Xi-Xj)/sqrt(...) + B * SUM_i!=j(Yi-Yj)/sqrt(...) + ...
完成此操作后，您可以看到，如果您计算了 A=1、B=C=D=0、B=1、A=C=D=0 和 C=1、A= 的值B=D=0 和 D=1，A=B=C=0，例如Qa、Qb、Qc、Qd，然后你可以找到 A、B、C 和 D 的任何其他值的值作为 A * Qa + B * Qb + C * Qc + D * Qd。
这将复杂度降低到 O(N^2)
关于algorithm - 查询 3d 点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32554822/