c++ - 在O(nlogn)中找到数组中的所有差异，其中n是元素的最大范围

问题:给定一个排序数组A，可以找到元素与A的所有可能差值，其中每个元素都是[1，...，n]范围内的整数。另外，您可以假设没有重复项。因此，数组的最大大小将为注意:由于上述限制，可能的总差异将在[1，...，n-1]范围内。
示例(对于N = 12):

这个问题类似于this one，除了n是否。问题中元素的数量，而不是元素的上限。
在同一问题中，还有一个答案:https://stackoverflow.com/a/8455336/2109808
这个家伙声称可以使用fft和自卷积实际上在O(nlogn)中完成，但我不明白，而且在在线卷积计算器(如this one)上尝试时，这似乎也不正确。
那么，有人知道如何在O(nlogn)中实现吗？
先感谢您 :)

最佳答案

OP链接的This answer建议执行以下步骤:

假定数组中包含非重复元素，范围为[0，n-1]。*

创建一个长度为n的数组，其中索引与输入元素匹配的元素设置为1，其他元素设置为0。这可以在O(n)中创建。例如，在输入数组[1,4,5]中给定，我们创建一个数组[0,1,0,0,1,1]。

计算自相关函数。可以通过采用FFT，对幅度进行平方，然后采用IFFT来计算。这是O(n log n)。

对于与输入中存在的差异相对应的索引，输出为非零。索引为0的元素始终为非零，应忽略。查找和打印这些元素为O(n)。

请注意，此过程是不正确的，因为通过FFT计算的自相关函数是循环的。也就是说，给定一个具有两个值0和n-1的输入数组，输出将在索引1以及索引n-1处具有一个非零元素。为避免这种情况，有必要在步骤＃2中将数组的长度设为2n，将其中一半设置为0。然后应忽略输出数组的后一半。将数组大小加倍不会改变算法的计算复杂度，仍然是O(n log n)。
*为了简单起见，我更改了OP给定的范围，通过向所有索引添加偏移量来更改此范围是微不足道的。