00:00
好,同学们,我们继续,通过上一讲,我们已经明白,确实已经完成了,但是这个算法并不最优,那么接下来我们是不是要写第二个版本,搞定它的最优算法?尽量的不要用两个负循环,一次就能找到是不是最爽好,那么在这个开始之前。告诉大家怎么用这个利寇这个网站啊,刚才同学也有问过。首先你登录以后该注册注册,这个不用我废话吧,那么他给你写好了,你自己可以在这憋。这是用它的编辑器。第二种呢,就是像杨哥这样的啊,你在idea里面先编好粘贴过去,看看你写的对不对,那么。一张过来,OK,那么这点一下执行代码,那么同学们请看。没问题吧,刷成绿色了。测试用例输入参数是一个numbers的数组,Target是九代码执行结果输入是这个。输出是零,跟一预期结果是一样的,这一波OK,那么当然立扣呢,在线的功能也很优秀,很复杂,那么可以调试啊,当然这个什么所谓前晚升级是不是要。
01:11
买单花点钱能跟上,那么这个呢,就看你自己了,如果说土豪玩家呢,该充值充值啊。我就不废话了,那么接下来回到我们这儿,第二种算法我们来解决一下,那么是吧,更优的解法通过哈希来完成。为什么会想到哈希呢?我们刚才说过了,他目前的。算法复杂度是不是?On的平方,那么我们希望就是什么,我们都明白,按照我们说过三个算法复杂度啊,这个呢,杨哥呢在课上给大家讲过大O的表示法,对吧。最好的是哪个,是不是OG能跟上,那么。其次是什么?是不是裸格2N这种算法,裸格以二为底的N对不对?比方说裸格288条记录,我们在买CQ索引上讲过,可能找三次就找得到,那么第三种啊,那么我们大一点的是不是OI。
02:09
这个更恐怖,都已经到什么两个负循环是不是N的平方了,所以说我们最好的算法是不是靠着这个最好找一次就找到,我们原来讲过找一次就能找到的话,哪个。最爽是不是就是我们找一次就能找到的话,我们讲过RA里面是有个东西叫K键之对也这叫RA放到我们Java是不是我们的哈。好,整明白思路以后,我们回到我们的。编程。那么接下来。那么直接呢,把这个呢。拷贝。这是我们的第二种算法,那么哈希希望它得到的效果就要比上面更强。性能。更好。那么怎么玩呢?直接。Map。
03:02
因为要返,因为要返回下标。我这呢就两个数字了,那么我们来放分析啊,Map,我们用个最简单的哈希map啊,因为这块就是一个算法,不用考虑并发性了这些,那么更复杂啰嗦的情况就不要,我就没有用con哈map啊,这块的话你用哪个都行哈,都可以。那么一样。跑不掉,只要是宿主,你肯定要挨个挨个的去变力嘛,所以说这个时候我们是不是负循环。直接也就拿过来这一波同学们。没问题吧?那么接下来还是我们刚才那个思路啊,如果说这个target,我们就拿我们的目标值啊,从头到尾挨个挨个去找。如果说找完了以后,比方说啊,要是现在的值要是九九减二是不是。得到我们这个七,那么也跟刚才一样,但是跟刚才完不同的地方是,如果说。
04:00
我们找得到。我们就要从哈斯map里面返回,那么找不到呢?我们就要先把第一次变利以后的结果存进这个哈希map里面,方便他第二次来查找好。那么什么意思呢?请看我写完啊。这波好说第一句话,第二句话,那么直接来变列,那也跟刚才一样,这个target去减我们的这个值,那么。我们这儿呢。过来我们这儿呢,就是比方说A加B等于C嘛,这个是partner。Number。OK,这是一个伙伴做没问题吧,啊,随便你叫什么名字。那么接下来我们来进行这个判断。假设我们的map里面干嘛含有我们的这个数字?我们呢,就返回我们这个数字的下标,这一波能跟上,你看现在哈希迈普刚刚整出来以后我们都。知道它是个什么,它现在是不是个几乎就是一个空对象里面什么都没有啊,那么所以说便利了以后,我们现在先相减,你这个map里面现在有没有。
05:10
这个值有没有在map里面呢?没有没有怎么办?没有我们是不是就把我们相关的东西先放进我们这个map里面,方便你第二次啊来进行查找,那放什么呢?我们现在九。现在I是零,整个值是几?是二。那么现在九减二这个partner伙伴数合作数就是A加B加C,这个伙伴是几?是不是九减二等于七,那么请问现在这个map里面有没有七?没有没有干什么?没有我就把它添到这个map里面。那么这个时候我们应该怎么填呢?我们想到的策略和套路是number,然后就把这个值放过来,然后再把它的下标。丢进来,好,那么请大家思考一下,我干了一件什么事?
06:05
哈希迈普是不是我们的?TV建制段,那么现在是这样啊。九减二等于七,这个map里面第一次执行的时候什么都没有吗?它包不包含不包含,所以说我们要便利,我们要便利,便利哪个便利等。值是要后续便利,我们的map里面去查找,找一次就能找到嘛,因为它是哈希,所以说找得到我就返回,那么现在没找到,我要存进去,存进去哈斯迈是K建值,对,那么我们现在九减。二。等于七,在这个里面没有七,所以说我们就把我们第一次变离的这个结果放进去,放谁这个T就是numbers I,这个值是解,是不是就是我们的二,所以说这个K就是我们的值,而这个value我们就把它当做是什么下标,这么说能跟上,那么请看啊,现在我们减了以后这个。
07:06
I下标是零,整个numbers I,它的值是不是就是我们的数组里面第一个元素二,我们变力是不是从头开始变利,那么找了以后,我们现在这个。哈希迈普里面啊。我们map的。T就是我们的这个值,下标是几,下标是不是就是我们的这个,哎,这一波能跟上好,那么。结束第一次循环,第二次循环再过来九减掉,现在这个I是几?这个I是不是应该是一了,第二次循环。一下标I是一,整体这个值是几?那么现在是不是七?那么请问九减去这个七等不等于二。那么现在就问问你,我们这个哈,Map里含不含有二这个T里面大家告诉我有没有,当然有了,所以说这个时候我们就爽了,我们是不是就可以又跟刚才一样返回去一个我们的。
08:08
数组,那么现在我们是不是就要把我们的map里面的get这个值,这个值是几啊?这个值是不是就是我们的这个帕合作数,然后再把当前便利的这个数字再返回,打完收工啊。思考一下啊,看一下我们的这个要求和这个想法,给大家点时间看看这个算法能不能理解,同学啊,我再来一次啊。我们第负循环第一次啊,9I下边是零,整个值是二,那么我们是不是从二从左。到要开始挨个挨个的并列,九减二是多少?是七第一次的时候啊,假设还没有这行代码的时候,Map里面是空的,有没有这个七,没有没有怎么办?没有的话呢,就说明什么九减二没有得到七,那么哪一个数。
09:07
做过测试,做过验证了,是不是下边是为零的这个二这个值啊,已经做过了,所以说没有找到对应的,那么我们就把这个map,就把这个二这个值啊作为K,你看二作为K这个值啊。放到这个map的key里面,再把R对应的下标就是这个I,现在就是什么我们的。第零个下标放进去能跟上好,第一次循环结束,第二次循环九,刚才测过二了,注意。二现在是不是已经存进来了?那么第二次的时候是什么?九减七等于多少二那么请问现在这个map里面含不含有二当然含有了,含有的话我们就把我们的值返回,那么。怎么返回?我们现在在map里面有没有二这个值啊,这个T以,所以说我们现在就把map里面这个二。
10:06
GET2返回这个整体都知道这个二返回和得到下边是几是不是零,但是由于我们是第二次变列,现在这个I是几是不是一啊?那么这样是不是就会得到了我们的最优的一个算法,因为这样的话,它是不是只需要一个for循环就能搞定,那么关键就是对这个哈map的灵活运用,那么同学们体会一下。好,那么同学们,我们现在换一下啊。跟刚才一样,现在呢?继续运行。按照我们第二种算法的话,那么同学们看一下能不能得到零跟一没有任何问题吧,那么一样,如果说现在我们的。二加上15,那么就等于我们的多少?17,那么是不是零和三啊,那么。我们来体会一把。大家看是不是下边是零跟三没有任何问题,所以说这个思路就是我们的最优的解法,那么它是不是要比上面这种两层负循环更加的。
11:10
精彩,更加的优化呀。所以呢。写不出来第二个直观的写法,那么同学们,我们写一个暴力的是吧,最经典的,最简单直接有效的,粗暴的,那么。下面呢,最优化的请同学们来看看,第二种只有一个for循环,我们呢一次啊就拿这个map。才搞定,那么所以说同学们。先写这个以后,那么让面试官觉得你还是有一定的基础,如果面试官问你说还有没有更优化的算法,那么同学们第二种是不是可以提供给你参考,那么顺便说一下。从这我们可以得到一个结论,如果你去大厂面试,面试官出的。算法题目是立扣的第一题。那说明什么,应该来说啊,因为大厂的流程最后压轴的肯定会是有一两个算法题,只要是算法题就行,那么但是面试官考虑你这么一个两数之和的这么一个算法,那说明应该来说哈,可能还是对你比较满意,对吧。
12:14
九大面试官放水想要你了。那么?你写出来就行了,OK,好,那么同学们,我们呢,对于两数之和相关的解答就给大家介绍到这儿,那么这两个务必请大家呢练练,那么从这我们可以得到什么结论,同学们。它的考察点是什么?根据结合上面,我们现在可以得到大厂的考察点。经典的GVM图书,经典的计算机知识的图书,你有没有读过?算法题有没有刷过立扣有没有登录过,你只要登录过立扣,第一道题两次求你马上哦,这个我刷过。所以说干嘛?你可别忘了你们的学长,这个题目我刷了,人家可是在默默的做着准备。那么。
13:01
所以。你都想来大厂啊,算法居然从来没有刷过,呵呵。所以呢,同学们,机会永远偏爱有准备的头脑。OK,好,感谢大家的聆听,今天我们就到这儿。
我来说两句