代码随想录训练营Day7:454四数相加II、383赎金信、15三数之和、18、四数之和

发布于:2022-12-04 ⋅ 阅读:(207) ⋅ 点赞:(0)

1.四数相加II:代码随想录 (programmercarl.com)

        1、此题相对于四数相加会更加简单,因为本题不需要去重,而四数之和需要去重。

        2、因为int的范围太大了,所以此题不能用数组,要考虑用set或者map

        3、因为不仅要考虑数值是否出现,还要考虑出现的次数,故要使用map

        4、思路:先遍历数组a,b,把数组a,b中的元素之和以及出现的次数放入map,然后遍历数组c,d,查看map中是否有0-(c+d)的值,若有则将count加上map【target】(即目标出现的次数)加粗的字数则是使用哈希法的原因。

        5.学会map【a+b】++,这种写法方式。

        6.第二个for循环中要遍历查找的target是0-(c+d)而不是0-(a+b)

2.赎金信代码随想录 (programmercarl.com)

        1.此题和之前的字母异位很像,用数组是因为数组比map速度更快。

3.三数之和代码随想录 (programmercarl.com)​​​​​

        1.在对num是【i】去重的时候,只能是nums[i] == nums[i-1] 而不能使nums[i] == nums[i+1],因为若有【-1,-1,2】的情况,nums[i] == nums[i+1]就把他给筛走了,而nums[i] == nums[i-1]就能避免这种情况。

        2.给left和right去重的时候,直接在找到合适的三个元素之后再去重,不用在没找到的时候就去重。

        3.记得找到答案之后left和right指针要同时收缩。尤其注意,收缩的操作只能在else语句里面完成,不能直接加在while循环的最后,因为若这样做的话,所有的if,else操作之后都会收缩指针,这是多余的操作,会产生错误。

        4.最后在对left和right去重的时候,要用while()循环,不能用for循环,防止多个相同数字排列在一起的情况

        5.在嵌套的while循环中,三种情况一定要分成,if、else if、else 而不能使if、if、else,这样会报错。

        6.嵌套循环中的条件为left < right 而不能是left <=right 因为若left ==right,那么这个时候nums【left】和nums【right】是同一个数,再加上nums【i】是两个数,而非三数。

        7.最后在去重left和right的时候,while循环的条件一定要加上left < right 不然会报错。

        刷题过程中犯得错误:3,4,7


 

4.四数之和:代码随想录 (programmercarl.com)​​​​​

        1、因为target可能为负数,故不能像之前三数之和一样剪枝,如【-4,-1,0,0】tar=-5,若像这样剪枝,则错过了这个情况。因而要像代码中那样剪枝来避免这种情况。

        2、在第二个for循环中做第二次剪枝的时候,nums【k】和nums【i】是一个整体。

·       3、在第二个for循环去重的时候,判断条件要为i>k+1;因为若==的话i-1==k,而其中的数不能为同一个数,所以这样才行。

        4、注意剪枝之后的操作是break(直接退出)而去重的操作是continue(进入下一次循环)且剪枝在去重之前操作

        5、知识点:为了防止溢出,要在判断left和right语句之前加上(long)

本文含有隐藏内容,请 开通VIP 后查看

网站公告

今日签到

点亮在社区的每一天
去签到