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)