如何以低于O(N²)时间复杂度生成数组两两和的N*N数组？

这个问题挺有意思的——常规的双重循环遍历所有元素对来计算和，时间复杂度确实是O(N²)，但如果想把复杂度降下来，**快速傅里叶变换（FFT）**是个绝佳的解决方案，它能利用卷积的特性，在O(M log M)的时间内搞定，只要M（所有可能和的取值范围大小）远小于N²，就能满足时间复杂度低于O(N²)的要求。

核心思路 #

两个数组的自卷积结果，本质上就是所有两两元素和的出现次数统计。FFT可以把卷积的计算时间从O(N²)压缩到O(M log M)，其中M是和的取值范围的长度。我们只需要先统计原数组中每个元素的出现次数，通过FFT计算自卷积得到每个和的出现次数，最后再根据次数展开成最终的数组B即可。

实现代码（Python） #

import numpy as np

def generate_pair_sum_array(A):
    if not A:
        return []
    
    # 确定原数组元素的范围，计算所有可能和的范围
    min_A = min(A)
    max_A = max(A)
    min_sum = 2 * min_A
    max_sum = 2 * max_A
    sum_range_size = max_sum - min_sum + 1
    
    # 创建计数数组，统计每个元素出现的次数（偏移min_A来缩小索引范围）
    count_array = np.zeros(sum_range_size, dtype=np.int64)
    for num in A:
        count_array[num - min_A] += 1
    
    # 利用FFT计算自卷积：卷积 = IFFT(FFT(a) * FFT(a))
    fft_count = np.fft.fft(count_array)
    fft_convolution = fft_count * fft_count
    convolution_result = np.fft.ifft(fft_convolution).real.round().astype(np.int64)
    
    # 根据卷积结果（每个和的出现次数）生成最终数组B
    result = []
    for idx in range(sum_range_size):
        current_sum = min_sum + idx
        result.extend([current_sum] * convolution_result[idx])
    
    return result

# 测试示例
if __name__ == "__main__":
    A = [1, 2]
    B = generate_pair_sum_array(A)
    print(B)  # 输出: [2, 3, 3, 4]

注意事项 #

• 适用场景：当原数组A的元素取值范围较小时，M远小于N²，FFT方法的效率会远高于双重循环。如果元素取值范围极大（比如元素是1e9级别），M会变得很大，此时FFT的时间可能不如O(N²)，需要根据实际场景选择合适的方法。
• 精度问题：逆FFT返回的是浮点数结果，所以需要用round()取整后转成整数，理论上所有结果都是整数，不会有精度误差。

内容的提问来源于stack exchange，提问作者Piyu