难在去重和剪枝！| LeetCode：18. 四数之和

我有四个蛋蛋:
去年秋招跟着代码随想录刷了200多道LeetCode，每道题刷了至少5遍，以至于某些题可以闭着眼睛写出来了，秋招也收割了一堆大厂offer，真的感谢[给心心]

【回复】哪200多题？这些题够进大厂吗
【回复】礼貌问问：收割了哪些大厂的offer呀？
澜渊wizard:
跟着刷了十几道题，卡哥的讲解思路真的很清晰，题目如果是死记硬背的话，就会陷入记忆和忘记的循环，觉得刷题特别痛苦......所以，还是要理解清楚。我做了三数之和后，看了这期视频，自己去写了四数之和，第一次提交就AC，看了眼力扣的评论区，痛苦的人好多，找到一个靠谱的思路，真的很重要！

够钟evil:
第一层剪枝判断直接return的条件里不需要一定target>0吧，前两个就够了

【回复】回复 @Historic_ : 如果nums【k】 > target, and targer >0, 则nums【k】肯定>0了，不需要&&nums【k】 > 0
【回复】我感觉是不需要num>0把[笑哭]
咪咪今天吃什么:
剪枝条件可以是4*nums【k】 > target。就是放缩，四个最小的如果都大于target，说明之后不可能相加等于target

【回复】回复 @42年的拉斐尔 : 提升一下类型 从int改用long long int
【回复】我也是这么想的，好像有问题
阿普之川普:
在C++代码中，为什么把第2级剪枝处理后的break;语句换成return result;会导致返回的结果有缺失呢，比如输入【-3,-2,-1,0,0,1,2,3】,target=0；输出缺少【-1,0,0,1】。

【回复】应该是二级剪枝直接return，第一层循环也提前终止了，这里就是当k=-2时，i遍历到了3，然后直接程序终止了，导致k都没有遍历到后面的-1。
【回复】确实，我没看视频，也是做完三数之和直接做四数之和，确实也出现了这样的错误，谢谢指导
gaojiawei:
大家看四数之和，有没有个疑问，nums排过序后，就是nums【k】>0了，为啥还要加上target>0呢？

【回复】如果target为-10，排序之后为【-4,-3,-2,-1】 只判断-4>target或者（-4+-3）>target就跳过了的话显然漏解了，因为后面还可以有负数，相加还是越加越小，所以即使是排过续，对于一个target为负数的情况下只判断一项两项的和不能直接枝剪去除
【回复】回复 @CalvinNier : 加上target>0会报错，例如这组数据int【】 nums = {1000000000,1000000000,1000000000,1000000000};int target=-294967296;剪枝都为false，走到left和right逻辑时，4个1000000000相加会溢出变成-294967296和target相等
【回复】也觉得奇怪，排序后，num【k] > 0了，就默认后面的数都是正数。target还有必要一定大于0吗？
S11ence丶:
好像不用剪枝也行，就是leetcode的最后一个用例int会溢出，给四数求和sum换个long类型就能通过，但是时间会慢一点[微笑]

张憨批啊:
自己试了一下，为什么在外层循环和内层循环其中任意一层循环调用剪枝操作就能通过呢，有大佬帮忙解答一下嘛

Cynic_TianLiang:
有没有好兄弟，纸质书上这道题的代码也是没有包含剪枝那两部分代码的？我买的应该是正版书。

【回复】回复 @段刀-来耶 : 剪枝就是提升运行效率吧。少检查点分支。没有答案也是对的，就是慢点
【回复】有的有的，我有点不太懂为啥要二级剪支
橘橘橘橘橘橘橘橘check:
[星星眼][星星眼][星星眼][星星眼]刷题[doge]过度到 无痛了 代码随想路yyds

果壳果壳果壳果:
讲得挺好的，非常适合我这种新手哈哈哈哈

胡噜娃老爷爷:
一刷留爪，没有做好剪枝，造成了这样int 溢出的测试结果 解答失败: 测试用例:【1000000000,1000000000,1000000000,1000000000】 -294967296 测试结果:[【1000000000,1000000000,1000000000,1000000000】] 期望结果:【】 stdout:

【回复】回复 @2MoonStop :其实说白还是，代码没有符合题目[笑哭]，注意到还是好点
【回复】这种用例就纯纯恶心人来的
慕晚翎:
为什么java代码进行第二次剪枝的操作 会报错 而C++却可以

【回复】回复 @北海长宁w :因为可能会出现right-1<=left，导致出现越界
【回复】回复 @紫金的心 : 佬，“right可能已经比后面的遍历所用到的left和right还大”是什么意思啊[大哭]right不是在后面才定义，然后初始值一直为nums.length - 1嘛[大哭]
【回复】回复 @紫金的心 : 模拟了下，原因是此时的right可能已经比后面的遍历所用到的left和right还大了，所以不能return,需要break继续遍历后面的第二层循环