算法的本质,就是构造解空间,然后根据解的特点,把不符合条件的解从中去掉。
就这个问题而言,我们从数组中取出一个数,那么我们如何判断这个数是不是两个数之一呢?
很明显,以现在的情况,还不能否定这个数,那么怎么办?
我们就要给这个数加上更多的身份,了解更多的信息,才能更好的判断。(这跟做事很像啊)
假设,我告诉你,这是这根数组中最小的数(记为A),我问你,这个最小的数能不能被你排除掉?
还是不能,因为这要取决另一个数。
好,那我们暂且认为这个数是,那么剩下的一堆数中再取出一个数(记为B),如何判断这个数要不要呢?
这时,就好办了,两个数一加,是就是,不是就不是。那完事之后呢,我们又不知道怎么办了,再从剩下的数组元素中取出一个数跟A合作?这样的方法,*都能想到。
现在的问题是,我们所作的工作(即取出两个数),没有拿到满意的解也就算了,对我们下一步也没有指导作用。(如果有,也不算白干啊,就当我交学费了啊)
那好,还是老方法,给他们加更多的信息,我们有方法,让取到的第二个数也有个身份,那该是什么身份呢?
可以推知,选择还是很多的,第二小的数,第三小的数,……最大的数
如果B为第二小的数
if A+B > sum 说明game over
if A+B = sum 也说明game可以over了
if A+B < sum 好吧,我打算试下一个
很明显,第三小的数也是这么搞,那如果B是最大的数呢?
if A+B < sum 虽然还没有搞出来,但说明一个问题,A不可能是两个数之一
if A+B = sum game可以over了
if A+B > sum 还好,这回可以把B给pass掉了
so,我想起来高中物理老师说的一句话,选择题如何做对啊?不选错的就可以了嘛!现在看来,不是废话啊!
说到这里,我们就有点感觉了,我们需要为数组的每个元素加上更多的身份信息:给他们排序。
排完序之后,搞两个“指针”,一个在左边往右走,一个在右边往左走。
记住,我们不是想要找到最后结果,我们只是想把不符合条件的踢出去。
小结:
这个方法不是我想的,我是在网上看的,感觉这个方法很巧,虽然它借鉴了快排的一些思路。然后,晚上没事干,加上了自己的想法,希望理解起来可以更平顺一点。由此可知,自己是个后知后觉的货,也不是研究算法的料,聊以为乐而已。