正在寻找算法或一些编码提示来找到解决方案
[a^3 + b^3 = c^3 + d^3，其中a, b, c and d全部在[1 .. 10000]范围内
这是面试问题。
我认为优先级队列至少要迭代a和b值。一些提示会很棒，将尝试从那里开始。
使用哈希映射存储(cube,(a,b))，您可以迭代所有可能的整数对，并在发现映射中已经存在所需的多维数据集之和后输出解决方案。
伪代码：
map <- empty hash_map<int,list<pair<int,int>>>
for each a in range(0,10^5):
for each b in range(a,10^5): //making sure each pair repeats only once
cube <- a^3 + b^3
if map.containsKey(cube):
for each element e in map.get(cube):
output e.first(), e.last(), a, b //one solution
else:
map.put(cube,new list<pair<int,int>>)
//for both cases, add the just found pair to the relevant list
map.get(cube).add(cube,new pair(a,b))
此解决方案是O（n ^ 2）空间（（1）和平均O（n ^ 2 + OUTPUT）时间，其中OUTPUT是输出的大小。
编辑：
所需空间实际上是O(n^2 logn)，其中n是范围（10 ^ 5），因为要表示10^5整数，您需要ceil(log_2(10^15)) = 50位。因此，您实际上需要大约500,000,000,000位（+映射和列表的开销），约为58.2 GB（+开销）。
因为对于大多数计算机来说，它有点太多-您可能要考虑将数据存储在磁盘上，或者如果您拥有64位计算机-只需存储在“内存”中，然后让OS和virtual memory系统按照尽力而为。
（1）正如编辑所阐明的，它实际上是O(n^2log(n))空间，但是如果我们将每个整数存储都作为O(1)（通常是这种情况），则会得到O(n^2)空间。显然，相同的原理将适用于时间复杂度。
使用优先级队列几乎可以肯定是最简单的解决方案，也是最实用的解决方案，因为它是O（n）存储（如果需要大数，则具有对数因子）。任何涉及计算所有可能总和并将其放入地图的解决方案都将需要O（n ^ 2）存储，这很快就变得不切实际。
使用哈希图（O（n ^ 2）解决方案：
比简单的解决方案更快的方法如下：计算a ^ 3 + b ^ 3可以具有的所有值，并随其存储a和b的所有可能值。这是通过循环遍历a和b，将结果（a ^ 3 + b ^ 3）存储在二叉树中并具有与每个结果相关的值列表（a和b）来完成的。
int Search(){
int MAX = 10000000;
for(int a = 0; a < MAX; a++){
int a3 = a * a * a;
if(a3 > MAX) break;
for(int b = a; b < MAX; b ++){
int b3 = b * b * b;
if(a3 + b3 > MAX)break;
for(int c = 0; c < a; c++){
int c3 = c*c*c;
int m = a3 - c3;
int d = b+1;
while(true){
int d3 = d * d * d;
if(d3-b3 <= m){
if((d3 - b3) == m){
count++;
PUSH_Modified(a3, b3, c3, b3, a, b, c, d);
}
d++;
continue;
}
else
break;
}
}
}
}
return 0;
让我们假设一个解决方案：
一个解决方案-使用在排序数组中找到2个和的概念。这是O（n3）
逻辑：a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3然后，a ^ 3 + b ^ 3-c * 3-d ^ 3 = 0尝试通过将a，b，c和d的值的所有组合置于[0，10 ^ 5]的范围内来求解该方程。如果方程式求解，则打印a，b，c和d
从蛮力方法开始，很明显它将执行O（n ^ 4）次。如果空间不是一个约束，我们可以将列表和地图结合起来。该代码是不言自明的，我们使用嵌套列表来跟踪特定总和（地图中的键）的所有条目。因此，时间复杂度从O（n ^ 4）降低为O（n ^ 2）