算法专题笔记------一篇讲明白 LeetCode三数之和与四数之和

算法专题笔记------三数之和与四数之和

题目描述：给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

力扣题目链接

三数之和

要想做出四数之和我们必须先彻底搞懂三数之和这道题目，他是我们做四数之和的基础，二者解法一脉相承

三数之和力扣链接

暴力解法

这种解法很容易想到 就是用三层for来遍历 穷举出所有三元组

for(inti=0;i<nums.length;i++){for(intj=i+1;j<nums.length;j++){for(intk=j+1;k<nums.length;k++){if(nums[i]+nums[j]+nums[k]==0){//将结果放入结果集}}}}return//结果集

暴力解法的时间复杂度是O(N^3)

双指针解法

在暴力解法中我们只是一味地遍历数组，但是其实有可能在第一层就可以给结果宣判死刑了这样就可以省去很多没必要的操作

因为暴力解法的时间复杂度已经飙到O(N^3)了，所以我们可以考虑先给数组排个序，排序操作的复杂度只有O(N*logN)来方便后续双指针操作

双指针核心思想

简单来说就是定一动二，既然结果是三元组那么我们就先定死一个数，然后再用剩下两个数去凑结果即可。对定一个数的代码实现很简单，就是for循环的的循环索引，对于“动二”操作就是双指针了,至于凑结果一会结合下面的代码讲解

可以先粗略浏览一下下面的代码片段：

int[]nums={-2,-1,0,1,2};//for循环负责 “ 定一 ”for(inti=0;i<nums.length;i++){intleft=i+1;intright=nums.length-1;//while循环负责 “ 动二 ”while(left<right){intsum=nums[i]+nums[left]+nums[right];//下面的 if--else 负责 “ 凑结果 ”if(sum>0){right--;}elseif(sum<0){left++;}else{//将结果记录下来 { nums[i], nums[left], nums[right] }right--;left++;}}}

相信看完上面的代码你能很清楚的看出来所谓的定一与动二是通过哪些语句操作的了现在的主要问题是让指针这么移动的逻辑是什么🧐。首先执行for循环的时候索引首先确定了sum变量的第一项以及left的位置，然后我们操作双指针的区间就确定为left~数组末尾，然后再看if--else结构是如何移动双指针的：

事先要先明确的是数组是从小到大排好序的

1. 结果大了(sum>0)
   • right左移nums[right]变小 ==》sum减小
2. 结果小了(sum<0)
   • left右移nums[left]变大 ==》sum变大
3. 找到目标三元组(sum==0)
   • 再让指针移动一次（不然会死循环）

小细节：while的执行条件不能是<=因为当left = right时结果就只剩两个数了

经过上面的操作我们就能找到一组包含i索引的全部结果了，再进行for就能找齐所有结果

去重操作

上面的解法对于数组{-2,-1,0,1,2}是成立的但是如果我把数组改为{-1,-1,0,1,2}
那么输出就变成了[ [-1,-1,2], [-1,0,1], [-1,0,1] ]了！很明显有一组出现重复了
这是为什么呢？

再看我们记录的解的形式{ nums[i], nums[left], nums[right] }因为当i = 0 和 i = 1时nums[i]都是 -1，所以就出现了重复结果，为了解决这个问题我们就想能不能让 i 直接跳到下一个和当前不同的值呢？至此数组的排序又发挥了巨大的作用：所有相同的值都挨在一起！所以可以写出代码：

if(i>0&&nums[i]==nums[i-1]){continue;//值相同时就掠过当前索引}

我们又向胜利迈进了一步，可是力扣刁钻的测试还在追杀我们😭

再改一下数组{-2，0，0，0，2，2，2，2}输出：[ [-2, 0, 2], [-2, 0, 2], [-2, 0, 2] ]
又重复了！哈哈不过这难不倒聪明的鼠鼠，类比对索引i的去重 很容易写出对left和right的去重代码

while(left<right&&nums[left]==nusm[left+1]){left++;}while(left<right&&nums[right]==nums[right-1]){right--;}

至此去重操作全部完成了🥳

剪枝操作

轻舟已过万重山！剪枝操作可以进一步加快代码的运行效率，sum的目标值是0
那如果我们的索引i已经是一个大于0的数了，数组又是升序，那以后的值是不是就一定不行了呢？是的！所以剪枝代码如下：

if(nums[i]>0){returnret;}

现在我们拿下了力扣通过率仅有40.3%的三数之和😀接下来可以趁着手感火热一起秒掉通过率36.9%的四数之和

四数之和

sum = nums[i] + nums[j] + nums[left] + nums[right]

众所周知4 = 3 + 1，所以 四数之和 等于一数 + 三数之和，回忆一下刚才的三数之和我们输出了什么，是不是一组令sum = 0的三元组啊，那么现在只要找到令sum = 负的第一个数的三元组就能拼接成本题的答案了！

那怎么找第一个数呢？是不是在来一个for就可以了！

下面鼠鼠快速的带大家啊过一遍逻辑

暴力解法

四层forO(N^4)

双指针解法

双指针核心思想

这里只需要将原来的sum是否大于零改为是否大于负的第一个数即可,并由定一动二改为定二（i，j）动二（left，right）

去重操作

这里要注意：去重操作是从第二个位置开始的，在三数之和中i > 0因为零是第一个位置

if(i>0/*零是第一个位置*/&&nums[i]==nums[i-1]){continue;//值相同时就掠过当前索引}

写四数之和时我们的第二格数也就是j是从i + 1开始取的，所以要写j > i + 1

剪枝操作

这里你可能会想，我要如何剪枝呢，三数之和的时候很简单，只要第一个数大了那剩下的就不用看了。但是现在目标不是0了，目标是自定义的target变量还能剪枝吗？当然能！结果肯定越加越大啊那只要nums[i]>target我就剪枝。

==错了！==看下面数组：{-5,-4,-1, 1, 3, 8}, target = -10-5>-10但是如果剪枝就会错过正确答案，那什么时候剪枝呢？是不是从i=3即nums[i] = 1时就可以了。所以对i剪枝逻辑如下

if(nums[i]>target&&(nums[i]>=0||target>=0)){returnret;}

解决了如何剪枝，还要解决对谁剪枝，既然i可以剪枝那么j是不是也可以剪枝呢？是的！ 还记得定二动二吗？只要是定的就可以剪枝！剪枝的核心逻辑就是：一旦可以通过定下来的变量排除结果那动的变量就没必要动了

总结

这两道题的价值所在就是双指针，去重，剪枝与此同时对代码的边界处理也有很高的要求，鼠鼠刷这道题的时候也是一遍遍的调试代码才AC的。所以写这篇博客希望帮助到也在刷这道题的兄弟。

最后再把可以通过的Java代码贴出来吧，我没有对j进行剪枝，大家可以补充这部分代码片段到评论区哟😊

classSolution{publicList<List<Integer>>fourSum(int[]nums,inttarget){List<List<Integer>>ret=newArrayList<>();Arrays.sort(nums);for(inti=0;i<nums.length;i++){if(nums[i]>target&&(nums[i]>=0||target>=0)){returnret;}if(i>0&&nums[i]==nums[i-1]){continue;}intleft;intright;intj=i+1;for(;j<nums.length;j++){if(j>i+1&&nums[j]==nums[j-1]){continue;}left=j+1;right=nums.length-1;while(left<right){if(nums[j]+nums[left]+nums[right]+nums[i]<target){left++;}elseif(nums[j]+nums[left]+nums[right]+nums[i]>target){right--;}else{ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));while(left<right&&nums[left]==nums[left+1]){left++;}while(left<right&&nums[right]==nums[right-1]){right--;}right--;left++;}}}}returnret;}}