出租车编号是一个整数，可以两种不同的方式表示为两个整数立方体的总和：a^3+b^3 = c^3+d^3。设计一种算法来查找a，b，c和d小于N的所有出租车编号。
a^3+b^3 = c^3+d^3
请同时用N表示空间和时间的复杂性。我可以在空间上o(N^2.logN)及时做到这一点O(N^2)。
o(N^2.logN)
O(N^2)
到目前为止，我发现的最佳算法：
形成所有对：N^2 对总数进行排序：N^2 logN 查找小于N的重复项
N^2
N^2 logN
但这需要N^2空间。我们可以做得更好吗？
在任何情况下，该算法的时间复杂度都不得小于 O（N 2），因为您最多可以打印 O（N 2）个出租车编号。
从理论上讲，为了减少空间使用，您可以使用此处提到的建议：little link。基本上，我们的想法是首先尝试所有可能的对 a，b 并找到解决方案：
a = 1 −（p − 3 * q）（p 2 + 3 * q 2） b = -1 +（p + 3 * q）（p 2 + 3q 2）
a = 1 −（p − 3 * q）（p 2 + 3 * q 2）
b = -1 +（p + 3 * q）（p 2 + 3q 2）
然后，您可以使用以下命令找到合适的 c，d 对：
c =（p + 3 * q）-（p 2 + 3 * q 2） d =-（p-3 * q）+（p 2 + 3 * q 2）
c =（p + 3 * q）-（p 2 + 3 * q 2）
d =-（p-3 * q）+（p 2 + 3 * q 2）
并检查它们是否均小于N。这里的问题是，求解方程组可能会有些混乱（“有点”，我的意思是 非常 乏味）。
在 O（N 2）空间的解决方案要简单得多，它可能会是因为能够在合理的时间限制运行可能会被罚款与二次空间使用二次的时间复杂度什么效率不够高。
希望对您有所帮助！
