生成边长与对角线均为整数的长方体：如何优化时间复杂度？

先提个一眼能看到的bug：你代码最后return的是couples，但实际存结果的变量是good_couples，这会导致返回空数组，得先改过来。

接下来砍核心问题：你的三重循环是O(n³)复杂度，n=10000时总循环次数是1e12级别的，根本不可能跑完。必须从维度上减少循环层数，利用勾股数的预生成来避免重复计算，具体优化思路和代码如下：

核心优化逻辑 #

1. 预生成勾股数映射：提前把所有满足x² + y² = z²的(x,y)组合存在映射里，后续直接查表，不用每次计算判断。
2. 抛弃浮点数运算：用平方值判断是否为完全平方数，代替Math.sqrt后判断整数——浮点数在大数下有精度误差，而且运算速度更慢。
3. 用集合求交集：对于每个(a,b)勾股对，找同时满足和a、b构成勾股对的c，直接用集合的O(1)查找代替遍历所有c。
4. 去重减少计算量：规定a ≤ b ≤ c，避免生成重复的长方体组合（比如(1,2,3)和(2,1,3)本质是同一个），最后如果需要全排列再扩展即可。

优化后的代码 #

const generate_good_cuboid = (max = 10000) => {
  // 预生成1~max的平方数组，避免重复计算平方
  const squares = new Array(max + 1);
  for (let i = 1; i <= max; i++) {
    squares[i] = i * i;
  }

  // 预生成每个数对应的勾股伴侣：key是数x，value是所有满足x²+y²为平方数的y的集合
  const pythagoreanMap = new Map();
  for (let x = 1; x <= max; x++) {
    const xSq = squares[x];
    const partners = new Set();
    // y从x开始，避免重复(x,y)和(y,x)的冗余计算
    for (let y = x; y <= max; y++) {
      const sumSq = xSq + squares[y];
      // 判断是否为完全平方数：取整后平方对比原数
      const sqrtSum = Math.floor(Math.sqrt(sumSq));
      if (sqrtSum * sqrtSum === sumSq) {
        partners.add(y);
        // 同步给y的伴侣集合里加x
        if (!pythagoreanMap.has(y)) {
          pythagoreanMap.set(y, new Set());
        }
        pythagoreanMap.get(y).add(x);
      }
    }
    pythagoreanMap.set(x, partners);
  }

  const goodCuboids = [];
  // 遍历所有a ≤ b的勾股对
  for (let a = 1; a <= max; a++) {
    const aPartners = pythagoreanMap.get(a);
    if (!aPartners) continue;
    for (const b of aPartners) {
      if (b < a) continue; // 保证a ≤ b，避免重复组合
      const bPartners = pythagoreanMap.get(b);
      if (!bPartners) continue;
      // 找同时在a、b伴侣集合里且≥b的c（保证a ≤ b ≤ c）
      for (const c of bPartners) {
        if (c < b) continue;
        if (aPartners.has(c)) {
          // 计算对应的对角线
          const d = Math.floor(Math.sqrt(squares[a] + squares[b]));
          const e = Math.floor(Math.sqrt(squares[a] + squares[c]));
          const f = Math.floor(Math.sqrt(squares[b] + squares[c]));
          goodCuboids.push({ a, b, c, d, e, f });
        }
      }
    }
  }

  return goodCuboids;
};

// 测试调用（可以先调小max验证逻辑）
console.log(generate_good_cuboid(100));

额外性能细节 #

• 预计算平方数组：比每次调用Math.pow(i,2)快3倍以上，还避免了浮点数转换开销。
• Set的O(1)查找：判断c是否符合条件时，直接用has()代替循环遍历，速度提升显著。
• 减少重复组合：通过a ≤ b ≤ c的限制，计算量直接降到原三重循环的1/6左右（长方体的6种排列被合并成一种）。
• 提前终止无效分支：如果某个数没有勾股伴侣，直接跳过该数的后续循环。

原代码为什么完全跑不动 #

原代码是O(n³)复杂度，n=10000时总循环次数是1e12次——哪怕每秒跑1e8次循环，都要跑3小时以上，这显然不现实。优化后的代码是O(n²)量级，且因为勾股数的密度远低于n，实际运行次数会远小于n²，n=10000也能在合理时间内跑完。

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