2026-07-21：可由多种立方和构造的整数。用go语言，给定一个正整数上限 n，一个正整数 x 被称为“好整数”，当且仅当它可以表示为两组不同的正整数对 (a, b) 的立方和，其中 a 和 b

2026-07-21可由多种立方和构造的整数。用go语言给定一个正整数上限 n一个正整数 x 被称为“好整数”当且仅当它可以表示为两组不同的正整数对 (a, b) 的立方和其中 a 和 b 都是正整数且满足 a ≤ b。换句话说存在至少两种不同的 (a, b) 组合使得 x a³ b³。现在需要找出所有不超过 n 的好整数并将它们按从小到大的顺序以列表形式返回。1 n 1000000000。输入 n 4104。输出 [1729,4104]。解释在小于等于 4104 的整数中好整数包括17291³ 12³ 1729以及 9³ 10³ 1729。41042³ 16³ 4104以及 9³ 15³ 4104。因此答案是 [1729, 4104]。题目来自力扣3890。大体步骤如下一、预计算阶段init函数1. 确定枚举范围上限mx 1_000_000_000。对于a从1开始枚举直到a³ mx/2为止。为什么是mx/2因为我们要找a³ b³ ≤ mx且a ≤ b当a³本身就超过mx/2时即使最小的b a和也会超过mx所以无需继续枚举。2. 双层循环枚举所有(a, b)组合外层循环枚举a内层循环枚举b从a开始保证a ≤ b。内层循环终止条件是a³ b³ mx一旦超过就break内层循环。对每一对(a, b)计算x a³ b³并在一个哈希表cnt中统计该值出现的次数。3. 筛选好整数遍历哈希表cnt对于出现次数c 1的x说明它至少可以由两组不同的(a, b)表示因此将其加入goodIntegers列表。这里没有存储具体组合只关心出现次数是否大于 1。4. 排序用slices.Sort将goodIntegers从小到大排序以便后续二分查找。备注题目描述提到“两组不同的正整数对”代码中当c 1即判定为好整数。这是正确的因为枚举时保证了a ≤ b所以同一个x如果有多个计数必然对应不同的(a, b)组合组合无序但已通过a ≤ b规范表示。二、查询阶段findGoodIntegers函数1. 二分查找调用sort.SearchInts(goodIntegers, n1)在已排序的goodIntegers中查找第一个大于n的元素的下标i。由于goodIntegers是升序的所有下标 i的元素都≤ n。2. 返回结果返回切片goodIntegers[:i]即所有不超过n的好整数已经是有序的。三、主函数中的示例n 4104调用findGoodIntegers(4104)得到[1729, 4104]并打印。四、复杂度分析1. 预计算的时间复杂度外层循环a的范围a³ ≤ 5e8即mx/2所以a最大约∛(5e8) ≈ 793。内层循环b的范围对于每个ab从a开始直到b³ ≤ mx - a³。总枚举的(a, b)对的数量大约是所有满足a ≤ b且a³ b³ ≤ 1e9的组合数。这是一个二维区域内的整点数量级可以通过积分估计条件a³ b³ ≤ 1e9且1 ≤ a ≤ b。令u a³, v b³则u v ≤ 1e9且u ≤ vu和v是立方数。直接枚举点对数量级约为O(N^(2/3))这里N 1e9所以N^(2/3) (1e9)^(2/3) 1e6级别。实际上这样的整数对数量大约是几十万到一百万左右。每次计算a³ b³和哈希表操作为 O(1)所以预计算的总时间在可接受范围内记为O(M)其中 M 是满足条件的(a, b)对的数量约 10^5 ~ 10^6。2. 预计算的空间复杂度哈希表cnt存储所有可能的a³ b³值不同值的数量小于等于 M也是O(M)。goodIntegers存储出现次数 1 的值数量远小于 M题目提到共 1554 个可视为 O(G)G 是好整数数量。整体额外空间复杂度为O(M)。3. 单次查询的时间复杂度只有一次二分查找sort.SearchInts时间复杂度O(log G)G ≈ 1554几乎常数时间。空间复杂度返回切片可直接引用全局数组的部分没有额外分配O(1)额外空间。总结总时间复杂度预计算 O(M)约 10^5 ~ 10^6 级别单次查询 O(log G)几乎常数。总额外空间复杂度O(M)主要是哈希表存储所有不同立方和的计数。Go完整代码如下packagemainimport(fmtslicessort)vargoodIntegers[]int// 1554 个funcinit(){constmx1_000_000_000cnt:map[int]int{}fora:1;a*a*amx/2;a{forb:a;a*a*ab*b*bmx;b{cnt[a*a*ab*b*b]}}forx,c:rangecnt{ifc1{goodIntegersappend(goodIntegers,x)}}slices.Sort(goodIntegers)}funcfindGoodIntegers(nint)[]int{i:sort.SearchInts(goodIntegers,n1)returngoodIntegers[:i]}funcmain(){n:4104result:findGoodIntegers(n)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-definit_good_integers():初始化好整数列表这些数可以用至少两种方式表示为两个立方数之和mx1_000_000_000cnt{}a1whilea*a*amx//2:bawhilea*a*ab*b*bmx:vala*a*ab*b*b cnt[val]cnt.get(val,0)1b1a1good_integers[]forx,cincnt.items():ifc1:good_integers.append(x)good_integers.sort()returngood_integersdeffind_good_integers(n,good_integers):返回所有不大于 n 的好整数result[]forxingood_integers:ifxn:result.append(x)else:breakreturnresultdefmain():good_integersinit_good_integers()n4104resultfind_good_integers(n,good_integers)print(result)if__name____main__:main()C完整代码如下#includeiostream#includevector#includeunordered_map#includealgorithmusingnamespacestd;vectorintgoodIntegers;// 全局初始化器namespace{structInitGoodIntegers{InitGoodIntegers(){constintmx1000000000;unordered_mapint,intcnt;for(inta1;a*a*amx/2;a){for(intba;a*a*ab*b*bmx;b){intvala*a*ab*b*b;cnt[val];}}for(constauto[x,c]:cnt){if(c1){goodIntegers.push_back(x);}}sort(goodIntegers.begin(),goodIntegers.end());}}initGoodIntegers;}vectorintfindGoodIntegers(intn){autoitupper_bound(goodIntegers.begin(),goodIntegers.end(),n);intidxdistance(goodIntegers.begin(),it);returnvectorint(goodIntegers.begin(),goodIntegers.begin()idx);}intmain(){intn4104;vectorintresultfindGoodIntegers(n);cout[;for(size_t i0;iresult.size();i){coutresult[i];if(iresult.size()-1){cout, ;}}cout]endl;return0;}