2026-07-21：可由多种立方和构造的整数。用go语言，给定一个正整数上限 n，一个正整数 x 被称为“好整数”，当且仅当它可以表示为两组不|cnt|spiderlinebreak|下标|哈希表|复杂度|整数

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完整代码如下：

package main

 import (
    "fmt"
    "slices"
    "sort"
)

 var goodIntegers []int// 1554 个

 func init() {
    const mx = 1_000_000_000
    cnt := map[int]int{}
    for a := 1; a*a*a <= mx/2; a++ {
        for b := a; a*a*a+b*b*b <= mx; b++ {
            cnt[a*a*a+b*b*b]++
        }
    }

     for x, c := range cnt {
        if c > 1 {
            goodIntegers = append(goodIntegers, x)
        }
    }

     slices.Sort(goodIntegers)
}

 func findGoodIntegers(n int) []int {
    i := sort.SearchInts(goodIntegers, n+1)
    return goodIntegers[:i]
}

 func main() {
    n := 4104
    result := findGoodIntegers(n)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def init_good_integers():
    """初始化好整数列表，这些数可以用至少两种方式表示为两个立方数之和"""
    mx = 1_000_000_000
    cnt = {}
    a = 1
    while a * a * a <= mx // 2:
        b = a
        while a * a * a + b * b * b <= mx:
            val = a * a * a + b * b * b
            cnt[val] = cnt.get(val, 0) + 1
            b += 1
        a += 1
    good_integers = []
    for x, c in cnt.items():
        if c > 1:
            good_integers.append(x)
    good_integers.sort()
    return good_integers

 def find_good_integers(n, good_integers):
    """返回所有不大于 n 的好整数"""
    result = []
    for x in good_integers:
        if x <= n:
            result.append(x)
        else:
            break
    return result

 def main():
    good_integers = init_good_integers()
    n = 4104
    result = find_good_integers(n, good_integers)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  

  

  


 using namespace std;

 vector goodIntegers;

 // 全局初始化器
namespace {
struct InitGoodIntegers {
    InitGoodIntegers() {
        const int mx = 1'000'000'000;
        unordered_map 
 
 cnt; 
 

         for (int a = 1; a * a * a <= mx / 2; a++) {
            for (int b = a; a * a * a + b * b * b <= mx; b++) {
                int val = a * a * a + b * b * b;
                cnt[val]++;
            }
        }

         for (const auto& [x, c] : cnt) {
            if (c > 1) {
                goodIntegers.push_back(x);
            }
        }

         sort(goodIntegers.begin(), goodIntegers.end());
    }
} initGoodIntegers;
}

 vector 
 
 findGoodIntegers(int n) { 
 
    auto it = upper_bound(goodIntegers.begin(), goodIntegers.end(), n);
    int idx = distance(goodIntegers.begin(), it);
    return vector 
 
 (goodIntegers.begin(), goodIntegers.begin() + idx); 
 
}

 int main() {
    int n = 4104;
    vector 
 
 result = findGoodIntegers(n); 
 

     cout << "[";
    for (size_t i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) {
            cout << ", ";
        }
    }
    cout << "]" << endl;

     return 0;
}