如何将双重循环实现的全序列乘法优化为单循环？

你的需求是生成1到n中所有两两数字的乘积（包括自身相乘），虽然双重循环是最直观的实现方式，但确实可以用单循环来改写——不过要明确：时间复杂度依然是O(n²)，因为不管用几层循环，都需要处理n×n个乘积结果，只是循环的写法不同。

单循环实现思路 #

把所有(i,j)的组合映射到一个连续的索引k（从0到n²-1），通过数学计算从k反推出对应的i和j：

• i = (k // n) + 1 （整数除法，得到当前所在的“行”）
• j = (k % n) + 1 （取余运算，得到当前所在的“列”）

这样就能用一个循环遍历所有k值，逐个计算i*j。

代码实现 #

int total = n * n;
for(int k = 0; k < total; k++){
    int i = (k / n) + 1;
    int j = (k % n) + 1;
    // do i*j
}

补充说明 #

这种写法只是把双重循环的嵌套逻辑转换成了单循环的索引映射，并没有减少实际需要处理的运算量，所以时间复杂度还是O(n²)。如果你的核心诉求是降低时间复杂度，那这种写法帮不到你——因为要得到所有n²个乘积结果，理论上不可能低于O(n²)的时间复杂度，除非你不需要生成所有结果，而是有其他可以优化的计算目标（比如求所有乘积的总和、最大值等，这些可以用数学公式优化）。

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