从一个数组中找到和为定值的两个数

时间:2022-08-03 19:38:07
问题:从一个数组中,找出两个数,使其和满足一定的值sum。

算法的本质,就是构造解空间,然后根据解的特点,把不符合条件的解从中去掉。

就这个问题而言,我们从数组中取出一个数,那么我们如何判断这个数是不是两个数之一呢?

很明显,以现在的情况,还不能否定这个数,那么怎么办?

我们就要给这个数加上更多的身份,了解更多的信息,才能更好的判断。(这跟做事很像啊)

假设,我告诉你,这是这根数组中最小的数(记为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,我想起来高中物理老师说的一句话,选择题如何做对啊?不选错的就可以了嘛!现在看来,不是废话啊!

说到这里,我们就有点感觉了,我们需要为数组的每个元素加上更多的身份信息:给他们排序。

排完序之后,搞两个“指针”,一个在左边往右走,一个在右边往左走。

记住,我们不是想要找到最后结果,我们只是想把不符合条件的踢出去。


小结:

这个方法不是我想的,我是在网上看的,感觉这个方法很巧,虽然它借鉴了快排的一些思路。然后,晚上没事干,加上了自己的想法,希望理解起来可以更平顺一点。由此可知,自己是个后知后觉的货,也不是研究算法的料,聊以为乐而已。