求高效方案:从完美立方列表中找出三不同数和为完美立方的组合
高效实现方法优化思路
你原来的三重循环存在两个核心问题:一是时间复杂度为O(n³),当列表较长时(比如对应6000000以内的立方数,n约181,三重循环要执行约600万次),效率极低;二是没有判断三个数字是否不同,且用numpy.cbrt判断立方数可能存在浮点数精度误差。
下面是几种更高效的优化方案,核心思路是减少循环层数+利用集合快速查找+避免重复计算:
预处理:生成立方数集合与列表
先一次性生成所有符合条件的立方数,同时存入集合(支持O(1)时间查找)和列表,为后续操作打好基础:
max_cube = 6000000 # 计算最大底数,加1避免取整漏掉边界值 max_root = int(max_cube ** (1/3)) + 1 # 生成立方数列表和集合 cubes = [x**3 for x in range(1, max_root)] cube_set = set(cubes)
方案一:双重循环+集合查找(O(n²)复杂度)
先遍历所有两两不同的立方数对,计算它们的和,再检查是否存在第三个不同的立方数,使得三者之和也是立方数。通过索引范围限制避免重复计算:
result_sums = set() # 用集合存结果,自动去重 for i in range(len(cubes)): a = cubes[i] # 从i+1开始遍历,避免重复计算a和b的组合(比如a=1,b=8与a=8,b=1) for j in range(i+1, len(cubes)): b = cubes[j] sum_ab = a + b # 目标立方数d³必须大于sum_ab(因为c是正立方数) min_d = int(sum_ab ** (1/3)) + 1 for d in range(min_d, max_root): d_cube = d ** 3 c = d_cube - sum_ab # 检查c是立方数,且与a、b都不同,同时c>b保证三元组唯一不重复 if c in cube_set and c != a and c != b and c > b: result_sums.add(d_cube) # 输出排序后的结果 for s in sorted(result_sums): print(s)
方案二:反向遍历目标立方数(进一步减少无效计算)
先遍历所有可能的目标立方数d³,再找两个不同的立方数a、b,使得d³ - a - b也是一个不同的立方数,同时通过提前break跳过无效循环:
result_sums = set() for d_cube in cubes: for i in range(len(cubes)): a = cubes[i] if a >= d_cube: break # a已大于等于目标和,后续b更大,a+b必然超过d_cube,直接跳出 for j in range(i+1, len(cubes)): b = cubes[j] sum_ab = a + b if sum_ab >= d_cube: break # a+b已超过目标和,后续b更大,无需继续 c = d_cube - sum_ab # 检查c是立方数且与a、b都不同 if c in cube_set and c != a and c != b: result_sums.add(d_cube) for s in sorted(result_sums): print(s)
额外优化细节
- 去重处理:用集合存储最终结果,自动过滤不同三元组产生的相同和。
- 精度规避:用集合查找代替浮点数立方根判断,彻底避免精度误差。
- 循环剪枝:通过索引范围限制和提前break,跳过大量无需计算的无效情况。
内容的提问来源于stack exchange,提问作者Aayan Shaikh
相关产品推荐
相关产品推荐

