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 的整数中，好整数包括：

1729：1³ + 12³ = 1729，以及 9³ + 10³ = 1729。

4104：2³ + 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, n+1)，在已排序的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的范围：对于每个a，b从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 ≤ v，u和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("fmt""slices""sort")vargoodIntegers[]int// 1554 个funcinit(){constmx=1_000_000_000cnt:=map[int]int{}fora:=1;a*a*a<=mx/2;a++{forb:=a;a*a*a+b*b*b<=mx;b++{cnt[a*a*a+b*b*b]++}}forx,c:=rangecnt{ifc>1{goodIntegers=append(goodIntegers,x)}}slices.Sort(goodIntegers)}funcfindGoodIntegers(nint)[]int{i:=sort.SearchInts(goodIntegers,n+1)returngoodIntegers[:i]}funcmain(){n:=4104result:=findGoodIntegers(n)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-definit_good_integers():"""初始化好整数列表，这些数可以用至少两种方式表示为两个立方数之和"""mx=1_000_000_000cnt={}a=1whilea*a*a<=mx//2:b=awhilea*a*a+b*b*b<=mx:val=a*a*a+b*b*b cnt[val]=cnt.get(val,0)+1b+=1a+=1good_integers=[]forx,cincnt.items():ifc>1:good_integers.append(x)good_integers.sort()returngood_integersdeffind_good_integers(n,good_integers):"""返回所有不大于 n 的好整数"""result=[]forxingood_integers:ifx<=n:result.append(x)else:breakreturnresultdefmain():good_integers=init_good_integers()n=4104result=find_good_integers(n,good_integers)print(result)if__name__=="__main__":main()

C++完整代码如下：

#include<iostream>#include<vector>#include<unordered_map>#include<algorithm>usingnamespacestd;vector<int>goodIntegers;// 全局初始化器namespace{structInitGoodIntegers{InitGoodIntegers(){constintmx=1'000'000'000;unordered_map<int,int>cnt;for(inta=1;a*a*a<=mx/2;a++){for(intb=a;a*a*a+b*b*b<=mx;b++){intval=a*a*a+b*b*b;cnt[val]++;}}for(constauto&[x,c]:cnt){if(c>1){goodIntegers.push_back(x);}}sort(goodIntegers.begin(),goodIntegers.end());}}initGoodIntegers;}vector<int>findGoodIntegers(intn){autoit=upper_bound(goodIntegers.begin(),goodIntegers.end(),n);intidx=distance(goodIntegers.begin(),it);returnvector<int>(goodIntegers.begin(),goodIntegers.begin()+idx);}intmain(){intn=4104;vector<int>result=findGoodIntegers(n);cout<<"[";for(size_t i=0;i<result.size();i++){cout<<result[i];if(i<result.size()-1){cout<<", ";}}cout<<"]"<<endl;return0;}