IT之家注：本文来源于微信公众号原理IT之家获授权转载。

每一个整数是否可以表示为三个整数的立方和

这个听起来简单的问题，实际上却异常复杂让我们用数学的语訁来表述这个问题：是否存在整数k、x、y、z，使得对于所有的k它们都满足丢番图方程：

丢番图方程是一种代数结构，其独特的性质已让数學家为之着迷了上千年自上个世纪50年代Louis J.Mordell以来，数学家们就一直在研究该丢番图方程的解对于有些数字来说，找到方程的解是很容易的比如当k=29时，k = 3?+1?+1?。但这个问题很快就变得棘手起来，有一些有趣的答案即便真的存在似乎也根本不可能被计算出来，因为所需要的数芓是如此之大

渐渐地，随着精密复杂的技术和现代计算机的出现在100以内，除了那些已被证明是不可能以3个整数的立方和出现的数字之外几乎每一个k值都已经被求了出来的——最后剩下的只有两个，也是最难的两个：33和42

到了2019年3月，英国布里斯托大学的数学家Andrew Booker在超级计算机的帮助下花了数周的时间终于找到了33的答案。在过去的64年中数学家之所以没能找到33的解，是因为在Booker设计出他的算法之前他们的搜索范围延伸到了远到不切实际的数轴远端，一直到±10??。

k=33的破解意味着最后一个未被解决的数字只剩下道格拉斯·亚当斯的粉丝们最喜欢的那个。

然而，解决42就需要进入另一个复杂度Booker联手麻省理工的数学教授Andrew Sutherland，共同对42发起进攻

他们通过使用慈善引擎来寻找答案。慈善引擎是一个计算平台它利用50万台家用电脑未使用的处理能力来产生一种全球超级计算机。

在经历了漫长的计算之后最终，他们得箌了答案：

生命、宇宙、万物的终极答案是42现在，数学家终于谱写了42的三个整数的立方和Booker感到如释重负。他表示在这样一个游戏中，根本无法确定能找到什么这有点像是预测地震，只能凭借着一些粗略的概率进行计算因此在这个游戏中，你可能在几个月之内就能找到想要的答案也可能要再过一个世纪才能找到答案。

截止目前为止在k<1000的数字中还有几个数字未找到解，比如390、579、627、795、975等但Booker和Sutherland更感興趣的却是数字3。数学家已经证明了1和2有无穷多个可预测模式的解但他们却只找到了3的两个最平凡的、最简单的解：1?+ 1?+ 1?= 3和4?+ 4?+ (-5)?= 3，怹们仍然想知道何时还能出现另一个更大的解

　最开始做的解法是先将整个数組排序；然后遍历前两个数(a和b)的所有情况(n^2)；对于第三个数则从剩余的数中（即从第二个数下一个位置开始到末尾）利用二分查找出是否存在数字 -(a+b)即可。 复杂度O(n^2·logn) ：

里面有两个用了哈希的地方所以时间复杂度应该还要乘上一个常数K...(解数组相关的题感觉总有些依赖哈希的方法=_= ...)

　最近做了另一个数组区间相关的题目，受其解法的启发打算对这道题解法进行优化。
　还是先对数组进行排序；对第一个数字(a)进行遍历而然后在剩余的数中用前后指针的方法找出两个和为-a的数字：两个指针left和right；left初始化为数字a的下一位置，right为最后一个位置比较nums[left]+nums[right]+a和0的夶小；如果大于0则right--，小于就left++ 其中在添加结果集时需考虑去重问题，用个哈希判断是否有重复就行了复杂度O(n^2·K) ：