Medium

题目描述

给定一个整数 n。

如果一个整数 x 满足以下条件，则认为它是"好"的：

  • 存在至少两个不同的对 (a, b) 使得：
    • a 和 b 是正整数
    • a <= b
    • x = a³ + b³

返回一个数组，包含所有小于等于 n 的"好"整数，按升序排列。

示例 1：

输入：n = 4104
输出：[1729,4104]
解释：
在小于等于 4104 的整数中，"好"整数有：
- 1729: 1³ + 12³ = 1729 且 9³ + 10³ = 1729
- 4104: 2³ + 16³ = 4104 且 9³ + 15³ = 4104
因此，答案是 [1729, 4104]。

示例 2：

输入：n = 578
输出：[]
解释：
没有小于等于 578 的"好"整数，所以答案是空数组。

约束条件：

  • 1 <= n <= 10⁹

解题思路

这道题要求找到所有能用至少两种不同方式表示为两个立方数之和的整数。

思路分析

核心思路：

  1. 枚举所有可能的正整数对 (a, b)，其中 a ≤ b
  2. 计算 a³ + b³，如果结果 ≤ n，则记录这个和值
  3. 使用哈希表统计每个和值出现的次数
  4. 筛选出现次数 ≥ 2 的和值，这些就是"好"整数

实现细节：

  • 由于 a ≤ b 且 a³ + b³ ≤ n，我们可以确定 a 的上界约为 ∛(n/2)
  • 对于每个固定的 a，b 的范围是 [a, ∛(n - a³)]
  • 使用哈希表记录每个立方和出现的次数
  • 最后收集所有出现次数 ≥ 2 的值并排序返回

时间复杂度优化： 通过数学分析，a 的最大值约为 ∛(n/2)，总的枚举次数是可控的，对于 n ≤ 10⁹ 的情况是可行的。

代码实现

class Solution {
public:
    vector<int> findGoodIntegers(int n) {
        unordered_map<long long, int> count;
        
        // 枚举所有可能的 (a, b) 对，其中 a <= b
        for (long long a = 1; a * a * a <= n; a++) {
            for (long long b = a; a * a * a + b * b * b <= n; b++) {
                long long sum = a * a * a + b * b * b;
                count[sum]++;
            }
        }
        
        vector<int> result;
        for (auto& [sum, freq] : count) {
            if (freq >= 2) {
                result.push_back(sum);
            }
        }
        
        sort(result.begin(), result.end());
        return result;
    }
};

class Solution:
    def findGoodIntegers(self, n: int) -> list[int]:
        count = {}
        
        # 枚举所有可能的 (a, b) 对，其中 a <= b
        a = 1
        while a * a * a <= n:
            b = a
            while a * a * a + b * b * b <= n:
                sum_val = a * a * a + b * b * b
                count[sum_val] = count.get(sum_val, 0) + 1
                b += 1
            a += 1
        
        # 收集出现次数 >= 2 的值
        result = [sum_val for sum_val, freq in count.items() if freq >= 2]
        return sorted(result)

public class Solution {
    public IList<int> FindGoodIntegers(int n) {
        Dictionary<long, int> count = new Dictionary<long, int>();
        
        // 枚举所有可能的 (a, b) 对，其中 a <= b
        for (long a = 1; a * a * a <= n; a++) {
            for (long b = a; a * a * a + b * b * b <= n; b++) {
                long sum = a * a * a + b * b * b;
                count[sum] = count.GetValueOrDefault(sum, 0) + 1;
            }
        }
        
        List<int> result = new List<int>();
        foreach (var kvp in count) {
            if (kvp.Value >= 2) {
                result.Add((int)kvp.Key);
            }
        }
        
        result.Sort();
        return result;
    }
}

var findGoodIntegers = function(n) {
    const count = new Map();
    
    // 枚举所有可能的 (a, b) 对，其中 a <= b
    for (let a = 1; a * a * a <= n; a++) {
        for (let b = a; a * a * a + b * b * b <= n; b++) {
            const sum = a * a * a + b * b * b;
            count.set(sum, (count.get(sum) || 0) + 1);
        }
    }
    
    const result = [];
    for (const [sum, freq] of count) {
        if (freq >= 2) {
            result.push(sum);
        }
    }
    
    return result.sort((a, b) => a - b);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n^(2/3))
空间复杂度O(n^(2/3))

说明：

  • 时间复杂度：外层循环 a 的范围约为 ∛n，内层循环 b 的范围平均也约为 ∛n，总体复杂度为 O(n^(2/3))
  • 空间复杂度：哈希表存储的立方和个数最多为 O(n^(2/3))，用于存储结果的数组大小也是这个量级