Let 't' be a good number if 't' can be written as sum of 2 cubes in at least 2 distinct ways. Given n, write a method which prints all good numbers up to and including n.
“好数”的定义：假如一个数t能用至少两种不同的方式写成两个三次方数的和，就称其为“好数”。给一个整数n，求所有的小于等于n的“好数”。
1. 询问
n能不能是负数？假设不可以，否则负无穷到0这一块都得考虑。假设n为正整数。
两个三次方数能不能一样？假设不可以。
两个三次方数是正整数吗？假设是的。
2. 分析
暴力破解
首先对于某个数x，怎么判断其是不是“好数”？暴力破解自然就是把所有可能的数都过一遍，因为x=a3+b3=c3+d3，而已经假设abcd都是正整数，那么有abcd都小于x的三次方根。那么就在这个区间内用双指针找，然后找至少两组满足条件的，也就是x^(2/3)。
然后到这道题，要找出所有的好数，所以非常朴素地把区间内所有的数都用上面所讲的方法过一遍，也就是1(2/3)+2(2/3)+...+n^(2/3)，这个复杂度是多少？反正不低就是了。
如何改进
上面的方法当然有很多重复计算，因此可以用一个哈希表把计算结果存起来，然后看看有没有相等的，相等的就是“好数”了。这样只需要用n范围内的双指针跑一圈，时间复杂度O(n(2/3))，空间复杂度O(n(2/3))。
3. 代码
class Solution:
def goodNumber(self, n):
d = {}
i = 1
res = []
while i**3 < n:
j = i
while i**3 + j**3 <= n:
s = i**3 + j**3
if s in d:
d[s] += 1
res.append(s)
else:
d[s] = 1
j += 1
i += 1
return res
4. 总结
难度easy。
